Educational Codeforces Round 21 E: Selling Souvenirs

エディトリアル見て書いたコード。コメントつき

/*
エディトリアルのとおりの解法
*/
/*
重さ1, 2のsouvenirだけを使ったとき、重さの和がiとする。
このときdp[i]=(x,y,z)は以下の意味。
xはコストの和の最大値
yは重さ1のsouvenirをいくつ使ったか。
zは重さ2のsouvenirをいくつ使ったか。

インデックスのほうにy,zのような情報を持たせないで、最適値の後ろにくっつけてる。
*/
tuple<ll, int, int> dp[300001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;

    vll weight(N), cost(N);
    rep(i, N) {
        cin >> weight[i] >> cost[i];
    }

    // 重さの種類は3種類しかないのでバケツソートしておく。
    vll costByWeight[4];
    rep(i, N)costByWeight[weight[i]].push_back(cost[i]);
    // とりあえず、コストの大きい方から使いたいのでソートしておく。
    rep(i, 4)sort(costByWeight[i].rbegin(), costByWeight[i].rend());

    FOR(i, 1, M + 1)dp[i] = mt(-1ll, -1, -1);

    rep(i, M) {
        ll sumCost;
        int cnt1, cnt2;
        tie(sumCost, cnt1, cnt2) = dp[i];
        if (sumCost == -1)continue;
        if (cnt1 < sz(costByWeight[1])) {
            smax(dp[i + 1], mt(sumCost + costByWeight[1][cnt1], cnt1 + 1, cnt2));
        }
        if (cnt2 < sz(costByWeight[2]) && i + 2 <= M) {
            smax(dp[i + 2], mt(sumCost + costByWeight[2][cnt2], cnt1, cnt2 + 1));
        }
    }

    /*
    maxCost[i]は1,2の重さのsouvenirだけ使ったとき、重さの和がi以下である場合のコストの最大値
    */
    vector<ll> maxCost(M + 1);
    rep(i, M) {
        maxCost[i + 1] = max(maxCost[i], get<0>(dp[i + 1]));
    }

    // sumThreeは重さ3のsouvenirのコストの和
    ll answer = 0, sumThree = 0;
    // 重さ3のsouvenirのコストを総当りで固定する
    for (int i = 0; i <= M && i / 3 <= sz(costByWeight[3]); i += 3) {
        // 事前に計算したDPをうまく使って、解を更新する
        smax(answer, sumThree + maxCost[M - i]);
        if (i / 3 < sz(costByWeight[3])) {
            sumThree += costByWeight[3][i / 3];
        }
    }
    cout << answer << endl;
}
広告を非表示にする