AOJ 2642 Dinner

自炊する日を{ \displaystyle a_0,a_1,...,a_{k-1}}の{ \displaystyle k}日間(日は0-indexed)とし、{ \displaystyle S = \sum_{i=0}^{N-1} C_i}とおくと幸福度は{ \displaystyle S+\sum_{i=0}^{k-1}\{P(Q-a_i+2i)-C_{a_i}\} = S+kPQ+Pk(k-1)-\sum_{i=0}^{k-1}\{Pa_i+C_{a_i}\}}
よってkを固定した時、P*i+C[i]が小さいものから順にk個選ぶのが最適。

ちゃんと定式化するの大事…

ll N,P,Q;
ll C[500100];
vector<ll> vec;
int main(){
	scanf("%lld %lld %lld",&N,&P,&Q);
	ll sum = 0;
	for(int i=0;i<N;i++){
		scanf("%lld",&C[i]);
		sum += C[i];
		vec.pb(P*i+C[i]);
	}
	sort(all(vec));
	for(int i=1;i<vec.size();i++)vec[i]+=vec[i-1];
	ll ans = sum;
	for(int i=1;i<=N;i++)chmax(ans,sum+i*P*Q+P*i*(i-1)-vec[i-1]);
	cout << ans << endl;
	return 0;
}