AOJ 2642: Dinner

自炊が疎なときを思い浮かべるとやりやすい。

#include<stdio.h>
#include<algorithm>
using namespace std;
long long d[510000];
pair<long long,int> e[510000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++)scanf("%lld",d+i);
	long long ret=-999999999999999LL;
	long long sum=0;
	for(int i=0;i<a;i++){
		e[i]=make_pair(d[i]+(long long)i*b,i);
		sum+=d[i];
	}
	std::sort(e,e+a);
	for(int i=0;i<=a;i++){
		//printf("%lld\n",sum);
		ret=max(ret,(long long)i*(i-1)*b+sum+(long long)b*c*i);
		if(i<a){
			sum-=d[e[i].second];
			sum-=(long long)e[i].second*b;
		}
		
	}
	printf("%lld\n",ret);
}