結果

問題 No.31 悪のミックスジュース
ユーザー codershifthcodershifth
提出日時 2015-07-31 07:20:31
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 4,017 bytes
コンパイル時間 2,038 ms
コンパイル使用メモリ 148,232 KB
実行使用メモリ 4,376 KB
最終ジャッジ日時 2023-10-12 17:18:00
合計ジャッジ時間 2,350 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,368 KB
testcase_01 AC 2 ms
4,368 KB
testcase_02 AC 3 ms
4,372 KB
testcase_03 AC 3 ms
4,372 KB
testcase_04 AC 3 ms
4,368 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 2 ms
4,372 KB
testcase_07 AC 2 ms
4,368 KB
testcase_08 AC 1 ms
4,368 KB
testcase_09 AC 3 ms
4,368 KB
testcase_10 AC 1 ms
4,372 KB
testcase_11 AC 2 ms
4,372 KB
testcase_12 AC 2 ms
4,368 KB
testcase_13 AC 1 ms
4,368 KB
testcase_14 AC 2 ms
4,368 KB
testcase_15 AC 2 ms
4,372 KB
testcase_16 AC 2 ms
4,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class EvilMixJuice {
public:
    void solve(void) {
            int N;
            ll  V;
            cin>>N>>V;
            vector<ll> C(N);
            REP(i,N)
                cin>>C[i];

            if (V <= N)
            {
                // 全てのジュースを 1 リットルずつ買って等分をまぜればよいだけ
                cout<<accumulate(RANGE(C),0LL)<<endl;
                return;
            }
            //
            // のこり V リットル分を
            //
            // p[0]>=p[1]>=...>=p[N-1]>=0
            // p[0]+...+p[N-1] = V
            //
            // なるように最小コストで買えばよい。
            //
            // 通常の dp でやると O(N*V) となってしまい TLE する。
            //
            // そこで S[i] = C[0]+...+C[i] として
            // (i+1) リットルをコスト S[i] で購入すると考える。
            //
            // 単価 S[i]/(i+1) が最小の (i+1,S[i]) を目一杯買えばよさそう。
            // ただし (i+1) の倍数リットルの購入だと過不足が生じてしまう。
            //
            // S[i]/(i+1) が最小の i を minI , m = (minI+1) とするとき
            // (m,S[m-1]) パック以外のパックをどれだけ買えばよいかを DP で計算する。
            //
            // m*k リットル買うとすると (k,S[k-1]) を m 個買うよりは安い
            // ので (m,S[m-1]) 以外の (k,S[k-1]) の購入総数は最大 m までと考えてよい
            //
            // このとき minI!=k のすべての (k,S[k-1]) の購入総量は最大 m*N となる。
            //
            // (1,S[0]) が最小の 1 リットルパックなので各 (k,S[k-1]) は最大 m*N 個買うことになる。
            //
            // よって時間計算量 O(m^2*N^2) <= O(N^4)
            //
            // 購入総数が m を超えてしまうなら (m,S[m-1]) パック 1 個におきかえればよいので
            // (m,S[m-1]) 以外のパックの購入総数は最大 m 未満である。
            //
            // よって O(N^3) で計算できる。
            //
            vector<ll> S(N,0);
            S[0] = C[0];
            FOR(i,1,N)
                S[i] = S[i-1]+C[i];

            // 必ず 1 リットル以上は買うので先に計算しておく
            V = max(0LL, V-N);

            // S[i]/(i+1) が最大となる minI を求める
            ll minI = -1;
            ll minS = (1<<30);
            REP(i,N)
            {
                if (minS*(i+1) >= S[i]*(minI+1)) // minS/(minI+1) >= S[i]/(1+i)
                {
                    minI = i;
                    minS = S[i];
                }
            }
            ll m   = minI+1;
            ll mN2 = max(m*N+1, V-(V-m*N)/m*m+1);

            // dp[i][j] := i 番目までの S を使って j リットル買うときの最小コスト
            vector<ll> dp(mN2+1,0);

            dp[0] = 0;
            for (ll i = 0; i < mN2; ++i)
                dp[i+1] = dp[i] + S[0]; // dp[i][j+1] = dp[i][j] + S[0]

            // O(N^3)
            for (ll i = 0; i < N; ++i)
            for (ll j = 0; j <= mN2; ++j)
            {
                ll k = min(mN2, j+(i+1));
                dp[k] = min(dp[k], dp[j]+S[i]);
            }
            // V のうち m*(N+1) までは dp で計算した結果を使う。
            // 残りを (m,S[m-1]) パックで買えるだけ買う
            ll  kk = max(0LL,(V-m*N)/m);
            cout<<kk*S[m-1]+dp[V-kk*m]+S[N-1]<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new EvilMixJuice();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0