ほぼレート通りの結果。
https://atcoder.jp/contests/arc128/tasks/arc128_c
問題
整数列Aが与えられる。
ここで、以下の実数列Xを作ったとする。
- Xの和はS
- Xは昇順で、0以上M以下
AとXの内積の最大値を答えよ。
解法
最終的にXがどうなるかというと、先頭何要素かが0、その後何要素かが等しい値で、残りがMになる。
(そうでない場合、少しXの配分をずらすことで、総和を減らさずに上記の形に持ち込める)
そこで、0とMの個数を総当たりしてみるとよい。
int N,M,S; int A[5050]; ll TS[5050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>S; FOR(i,N) { cin>>A[i]; } reverse(A,A+N); double ma=0; FOR(i,N) { TS[i+1]=TS[i]+A[i]; } double ret=0; FOR(x,N+1) for(y=0;x+y<=N;y++) { if(x*M>S) continue; double lef=min(S-x*M,y*M); double a=TS[x]*M; if(y) { a+=lef/y*(TS[x+y]-TS[x]); } ret=max(ret,a); } _P("%.12lf\n",ret); }
まとめ
これは最終的に思いつけて良かったね。