タイトル名と問題内容の関係がよくわからなかった。
https://codeforces.com/contest/2154/problem/E
問題
N要素の整数列Aが与えられる。
以下の処理を最大K回まで行える時、Aの総和を最大化せよ。
Aのうちx(=奇数)個の要素を選び、それらをそのmedianに置き換える。
解法
Aを昇順に置いていたとする。
medianがA[i]となるようにする場合、m回目の処理ではA[(m-1)*(x/2)]...A[m*(x/2)-1]及びA[i]...A[i+(x/2)]を選ぶのが良い。
median A[i]を総当たりしながら、K回処理したときに上記置き換えによる結果が最大となるmを二分探索しよう。
int T,N,K; int A[202020]; ll S[202020]; ll hoge(int i,int l) { return S[N]-(S[i+l+1]-S[i+1])-S[l*K]+1LL*(K+1)*l*A[i]; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>K; FOR(i,N) cin>>A[i]; sort(A,A+N); FOR(i,N) S[i+1]=S[i]+A[i]; ll ret=S[N]; FOR(i,N) { int R=(i+K-1)/K; if(i+R<N) { ret=max(ret,1LL*(i+1+R)*A[i]+S[N]-S[i+1+R]); } } FOR(i,N) { int ma=min(i/K,(N-1-i)); if(ma<=100) { for(l=1;l<=ma;l++) ret=max(ret,hoge(i,l)); } else { int L=0,R=ma; while(R-L>=5) { int M1=(L*2+R)/3; int M2=(L+R*2)/3; ll v1=hoge(i,M1); ll v2=hoge(i,M2); ret=max({ret,v1,v2}); if(v1>=v2) R=M2; if(v2>=v1) L=M1; } for(l=L;l<=R;l++) ret=max(ret,hoge(i,l)); } } cout<<ret<<endl; } }
まとめ
手間取ったけどコードはDより短いんだな。