自炊が疎なときを思い浮かべるとやりやすい。
#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); }