yukicoder : No.2284 Assembly

これはすんなりだった。
https://yukicoder.me/problems/no/2284

問題

N人の人が縦に並んだ席に並ぶ。
N人は順に現れ、空いた席の先頭か末尾のいずれかに並ぶ。

各人iにはパラメータA[i],B[i]が設定されている。
最終的に人iが人jの前にいるとき、A[i]*B[j]だけスコアに計上するとき、最適な並び順のうちスコアの総和の最大値を求めよ。

解法

逆順に考えると、すでに並んだ人たちの前か後ろに並ぶことになる。
また、そのいずれであっても、後に並ぶ人との相対的な位置関係は変化しない。

ということで、逆順で並び順を考え、貪欲に前と後ろスコアが大きな方を選べばよい。

int N;
int A[202020],B[202020];


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

まとめ

★3でもだいぶ軽めな気がする。