AOJ 2642 Dinner

問題

Dinner | Aizu Online Judge

感想

これねー。

適当な基準を付けてソートするやーつ、ド典型ですが、むつかしいです。

自炊をするかどうかで自炊パワーが変動するので、ある日に自炊をしたら？しなかったら？みたいなのを考えてみたりします。

また、簡単なため、極端な例から見るとよさそうですね(すべて自炊、すべて外食みたいな)。

という第一感を持ち進めていくと。

すべて外食で済ませるというのをベースに、ある日自炊したときのscore変動についての評価が他の日をどうしたかを考えずにできることがわかります。

どういうことかというと、

i日目(0-index)に自炊した場合、他が全て外食だったとするとscoreの変動が-C_i + (Q - i) * pとなります。(この式をＡとします)

これをもとに複数日間自炊したときを考えると。

(k日間自炊したとすると)各日についてのＡが計算できていれば最後にk * (k - 1) * pを足すだけで計算でき、これはどの日に自炊したかに関係なく一定なので、結局各日にちについてＡのみを基準に自炊する日を決めてしまえることがわかります。(自炊したk日間を手前から見ていくと、二日目の自炊によるscore変化がA + 2 * p、三日目がA + 4 * p…となるのがわかるはず。)

そこまでわかれば、各日にちについてのAを計算してしまってから、大きい順に並べて、i日間自炊した際のscoreを見ていけば良さそうなのがわかりますね。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG_MODE
    #define DBG(n) n;
#else
    #define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007
 
typedef long long ll;
typedef pair<ll,ll> P;
 
int main(){
     
    ll n,q,p;cin >> n >> p >> q;
    vector<ll> v;
    ll sum = 0;
    REP(i,n){
        ll c;cin >> c;
        sum += c;
        v.PB(- c + (q - i) * p);
    }
     
    sort(ALL(v),greater<ll>());
     
    ll ans = sum;
         
    REP(i,n){
        sum += v[i];
        ans = max(ans,sum + i * (i + 1) * p);
    }
     
    cout << ans << endl;
     
    return 0;
}