Accepted/328K/141MS

poj1738.cpp

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int l[50005];
int n,m,ans;
void dfs(int k)
{
	int tmp=l[k]+l[k-1];
	ans+=tmp;
	m--;
	for (int i=k;i<m;i++)
		l[i]=l[i+1];
	int j=k-1;
	for (;j>0 && l[j-1]<tmp;j--)
		l[j]=l[j-1];
	l[j]=tmp;
	while (j>=2 && l[j]>=l[j-2])
	{
		tmp=m-j;
		dfs(j-1);
		j=m-tmp;
	}
}
void work(int n)
{
	for (int i=0;i<n;i++)
		scanf("%d",&l[i]);
	ans=m=0;
	for (int i=0;i<n;i++)
	{
		l[m++]=l[i];
		while (m>2 && l[m-1]>=l[m-3])
			dfs(m-2);
	}
	while (m>1)
		dfs(m-1);
	printf("%d\n",ans);
}
int main()
{
	int n;
	while ((~scanf("%d",&n)) && n)
		work(n);
	return 0;
}