結果
問題 | No.2701 A cans -> B cans |
ユーザー |
![]() |
提出日時 | 2024-10-08 08:16:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 263 ms / 1,000 ms |
コード長 | 1,314 bytes |
コンパイル時間 | 4,995 ms |
コンパイル使用メモリ | 315,780 KB |
実行使用メモリ | 199,040 KB |
最終ジャッジ日時 | 2024-10-08 08:17:10 |
合計ジャッジ時間 | 17,337 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 73 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#define pass (void)0#define INF (1<<30)-1#define INFLL (1LL<<60)-1using namespace std;using namespace atcoder;using mint = modint998244353;using ll = long long;int main() {int N, M;cin >> N >> M;vector<tuple<ll, ll, ll>> can(N);for (int i = 0; i < N; ++i) {ll A, B, C;cin >> A >> B >> C;can[i] = make_tuple(A, B, C);}vector<vector<ll>> dp(N+1, vector<ll>(M+1, -INF));dp[0][0] = 0;for (int i = 0; i < N; ++i) {ll A = get<0>(can[i]);ll B = get<1>(can[i]);ll C = get<2>(can[i]);ll first = A;ll second = A - B;for (int j = 0; j <= M; ++j) {if (dp[i+1][j] != -INF && j + second <= M) {dp[i+1][j + second] = max(dp[i+1][j + second], dp[i+1][j] + C * B);}if (dp[i][j] != -INF) {dp[i+1][j] = max(dp[i+1][j], dp[i][j]);if (j + first <= M) {dp[i+1][j + first] = max(dp[i+1][j + first], dp[i][j] + C * B);}}}}for (int i = 1; i <= M; ++i) {dp[N][i] = max(dp[N][i], dp[N][i-1]);}for (int i = 1; i <= M; ++i) {cout << dp[N][i] << "\n";}return 0;}