AtCoder ARC #092 : E - Both Sides Merger

今回しょうもないミスが多いなー。
https://beta.atcoder.jp/contests/arc092/tasks/arc092_c

問題

整数列Aがある。
この数列に対し、要素数が1になるまで以下の処理を繰り返す。

• 1つ要素を選ぶ。
  • その要素が両端なら選んだ要素を消す。
  • そうでなければ、要素を両隣の和で置き換え、両隣を消す。

残された要素の最大値を求めよ。

解法

残された要素は、元の整数列のいくつかの要素の和となる。
ではどの要素の和となるか。
答えを言ってしまうと、間に奇数個の要素を挟むように選んだいくつかの和である。

例えば要素がA,X,X,X,X,X,Bのように、AとBの和を取りたいが間に奇数個の邪魔な要素があったとする。
この場合、中央を取ることを繰り返せば最終的に(A+B)が残る。

また、両端を取ることで端の不要な要素も消すことができる。

int N;
ll A[1010];
ll dp[1010];
int from[1010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ma=-1LL<<60;
	int best=-1;
	
	for(i=1;i<=N;i++) {
		cin>>A[i];
		dp[i]=A[i];
		for(x=1;x<i;x++) if((i-x)%2==0) {
			if(dp[x]+A[i]>dp[i]) {
				from[i]=x;
				dp[i]=dp[x]+A[i];
			}
		}
		if(dp[i]>ma) {
			ma=dp[i];
			best=i;
		}
	}
	
	cout<<ma<<endl;
	vector<int> V;
	for(x=N;x>best;x--) V.push_back(x);
	while(from[x]>0) {
		y=from[x];
		while(y<x) {
			V.push_back((x+y)/2);
			x-=2;
		}
	}
	FOR(i,x-1) V.push_back(1);
	
	cout<<V.size()<<endl;
	FORR(v,V) cout<<v<<endl;
	
}

まとめ

これNが10^5だとまずいのかな。
検証が大変だったりする？