結果
問題 | No.2701 A cans -> B cans |
ユーザー |
![]() |
提出日時 | 2024-03-29 23:01:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 248 ms / 1,000 ms |
コード長 | 941 bytes |
コンパイル時間 | 2,006 ms |
コンパイル使用メモリ | 199,460 KB |
最終ジャッジ日時 | 2025-02-20 15:28:19 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 73 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> A(N), B(N); vector<long long> C(N); for(int i = 0; i < N; i++) { cin >> A[i] >> B[i] >> C[i]; } const long long INF = 1LL<<55; vector dp(N, vector<long long>(M+1, -INF)); { // init dp[0][0] = 0; for(int k = 1; k*A[0]-(k-1)*B[0] <= M; k++) { dp[0][k*A[0]-(k-1)*B[0]] = k*B[0]*C[0]; } } for(int i = 1; i < N; i++) { vector<long long> ep(M+1, -INF); for(int j = 0; j <= M; j++) { dp[i][j] = max(dp[i][j], dp[i-1][j]); dp[i][j] = max(dp[i][j], ep[j]); if(j+A[i] <= M) ep[j+A[i]] = max(ep[j+A[i]], dp[i-1][j]+B[i]*C[i]); if(j+A[i]-B[i] <= M) ep[j+A[i]-B[i]] = max(ep[j+A[i]-B[i]], ep[j]+B[i]*C[i]); } } long long ans = 0; for(int j = 1; j <= M; j++) { ans = max(ans, dp[N-1][j]); cout << ans << endl; } } /* -0 : +0 (k-1)*B[i]-k*A[i] : k*B[i]*C[i] */