結果
問題 | No.2701 A cans -> B cans |
ユーザー |
|
提出日時 | 2024-10-16 08:39:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,108 bytes |
コンパイル時間 | 1,072 ms |
コンパイル使用メモリ | 98,644 KB |
実行使用メモリ | 199,552 KB |
最終ジャッジ日時 | 2024-10-16 08:39:50 |
合計ジャッジ時間 | 17,600 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 53 WA * 20 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {int N, M;cin >> N >> M;// dpテーブルとA配列をlong long型に変更vector<vector<long long>> dp(N + 1, vector<long long>(M + 1, 0));vector<vector<long long>> A(N + 1, vector<long long>(3));// 入力処理for (int i = 1; i <= N; i++) {for (int j = 0; j < 3; j++) {cin >> A[i][j];}}// DP計算for (int i = 1; i <= N; i++) {for (int j = 1; j <= M; j++) {dp[i][j] = dp[i - 1][j]; // まずは前の行の値を引き継ぐif (j >= A[i][0]) { // A[i][0]が使える場合long long k = (j - A[i][0]) / (A[i][0] - A[i][1]); // kを計算// dpテーブルの更新、より大きな値を選択dp[i][j] = max(dp[i][j], dp[i - 1][j - A[i][0] - k * (A[i][0] - A[i][1])] + (k + 1) * A[i][1] * A[i][2]);}}}// 結果出力for (int j = 1; j <= M; j++) {cout << dp[N][j] << endl;}return 0;}