結果
問題 | No.2701 A cans -> B cans |
ユーザー |
![]() |
提出日時 | 2024-12-09 10:49:59 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,156 bytes |
コンパイル時間 | 2,151 ms |
コンパイル使用メモリ | 205,860 KB |
実行使用メモリ | 198,912 KB |
最終ジャッジ日時 | 2024-12-09 10:50:17 |
合計ジャッジ時間 | 16,452 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 6 |
other | WA * 73 |
ソースコード
#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;//i番目の店で1個も交換しないfor (int j=0; j<=M; j++) dp[i][j] = max(dp[i][j], dp[i-1][j]);//まずは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);}}ll mx = 0;for (int i=1; i<=M; i++){mx = max(mx, dp[N][i]);cout << mx << endl;}return 0;}