Codeforces #625 Div1 A. Journey Planning

割と簡単目な問題を落としてしまった回。
https://codeforces.com/contest/1320/problem/A

問題

N要素の数列Bが与えられる。
ここで、いくつかの要素を選択したとする。
その時の要素のindexを昇順に並べた数列をCとする。
C[i+1]-C[i]=B[C[i+1]]-B[C[i]]を満たすCの選び方のうち、B中で選んだ要素の和の最大値を求めよ。

解法

D[i]=B[i]-iとすると、Dにおいて一致する要素をできるだけ多く選ぶのが良い。
そこでD[i]が一致するiにおけるB[i]の総和を求め、その最大値を取ろう。

int N;
int B[202020];
ll V[810000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>B[i];
		V[B[i]-i+400000]+=B[i];
		ret=max(ret,V[B[i]-i+400000]);
	}
	cout<<ret<<endl;
	
}

まとめ

コードにすると短い。