AtCoder ABC #163 : E - Active Infants

EとFにだいぶ難易度差を感じた。
https://atcoder.jp/contests/abc163/tasks/abc163_e

問題

N要素の整数列Aが与えられる。
この数列を並べ替えた数列A'を考える。
A[i]がA'においてj番目に移動したとき、A[i]*abs(i-j)だけスコアが得られる。
スコアの最大値を求めよ。

解法

大きい値ほど大きく動かすのが良いため、大きい値から順に場所を考えていくと、左右両端から埋まっていくことに気付く。
f(L,R) := Aのうち大きな(L+R)要素について左右の埋め方を決め、左側L個、右側R個埋まった状態におけるスコアの最大値
とすると、f(L,R)からf(L+1,R)やf(L,R+1)を更新できる。

あとはf(k,N-k)の最大値を答えればよい。

int N;
pair<int,int> P[2020];
ll dp[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		P[i]={x,i};
	}
	
	sort(P,P+N);
	reverse(P,P+N);
	
	FOR(x,N+1) FOR(y,N+1) dp[x][y]=-1LL<<60;
	dp[0][0]=0;
	FOR(i,N) {
		ll k=P[i].first;
		r=P[i].second;
		for(x=0;x<=i;x++) {
			y=i-x;
			
			dp[x+1][y]=max(dp[x+1][y],dp[x][y]+abs(r-(x))*k);
			dp[x][y+1]=max(dp[x][y+1],dp[x][y]+abs(r-(N-1-y))*k);
			
		}
	}
	
	ll ret=-1LL<<60;
	FOR(x,N+1) ret=max(ret,dp[x][N-x]);
	cout<<ret<<endl;
	
}

まとめ

これがこの正答数なのは意外。unratedのせい？