結果
問題 | No.2741 Balanced Choice |
ユーザー |
|
提出日時 | 2024-04-20 12:27:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 933 bytes |
コンパイル時間 | 939 ms |
コンパイル使用メモリ | 75,060 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 07:46:20 |
合計ジャッジ時間 | 1,514 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 2 |
other | WA * 10 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>using namespace std;struct stone {int type;int weight;int value;};int knapsack(const vector<stone>& stones, int c) {int n = stones.size();vector<int> dp(c + 1, 0);for (int i = 0; i < n; ++i) {int w = stones[i].weight;int v = stones[i].value;for (int j = c; j >= w; --j) {dp[j] = max(dp[j], dp[j - w] + v);}}return dp[c];}int main() {int n, w, d;cin >> n >> w >> d;vector<stone> stones(n);for (int i = 0; i < n; ++i) {cin >> stones[i].type >> stones[i].weight >> stones[i].value;}vector<stone> t_0, t_1;for (const stone& stone : stones) {if (stone.type == 0) {t_0.push_back(stone);} else {t_1.push_back(stone);}}int v1 = knapsack(t_0, w);int v2 = knapsack(t_1, w - d);int m_v = max(v1 + v2, v1 + knapsack(t_1, w));cout << m_v << endl;return 0;}