結果

問題 No.2701 A cans -> B cans
コンテスト
ユーザー srjywrdnprkt
提出日時 2024-12-09 11:04:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 293 ms / 1,000 ms
コード長 1,155 bytes
コンパイル時間 2,002 ms
コンパイル使用メモリ 197,308 KB
最終ジャッジ日時 2025-02-26 11:41:34
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 73
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    //店iでX回交換するのに必要な缶の数
    //(A-B)個補充すれば1回交換できる。(初めはA個)
    //A+(X-1)(A-B)個

    //dp(i, j)=i番目の店まででj個以下の缶で得られる嬉しさの最大値
    ll N, M, A, B, C;
    const ll inf = -1e18;
    cin >> N >> M;
    vector dp(N+1, vector<ll>(M+1, inf));
    dp[0][0] = 0;
    
    for (int i=1; i<=N; i++){
        cin >> A >> B >> C;
        //まずは1個買う
        for (int j=0; j<=M; j++){
            if (j-A>=0 && dp[i-1][j-A] != inf) dp[i][j] = max(dp[i][j], dp[i-1][j-A]+B*C);
        }
        //その後補充
        for (int j=0; j<=M; j++){
            if (j-(A-B)>=0 && dp[i][j-(A-B)] != inf) dp[i][j] = max(dp[i][j], dp[i][j-(A-B)]+B*C);
        }
        //i番目の店で1個も交換しない
        for (int j=0; j<=M; j++) dp[i][j] = max(dp[i][j], dp[i-1][j]);
    }

    ll mx = 0;
    for (int i=1; i<=M; i++){
        mx = max(mx, dp[N][i]);
        cout << mx << endl;
    }

    return 0;
}
0