結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
|
提出日時 | 2020-05-29 19:02:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 752 bytes |
コンパイル時間 | 887 ms |
コンパイル使用メモリ | 72,068 KB |
最終ジャッジ日時 | 2025-01-10 16:16:38 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <iostream> #include <vector> int W = 100000; void solve() { std::vector<int> dp(W + 1, 0); int n; std::cin >> n; while (n--) { int v, w; std::cin >> v >> w; for (int x = W; x >= w; --x) { dp[x] = std::max(dp[x], dp[x - w] + v); } } int min = W, max = 0; int v; std::cin >> v; for (int w = 1; w <= W; ++w) { if (dp[w] != v) continue; min = std::min(min, w); max = std::max(max, w); } std::cout << min << "\n"; if (max == W) { std::cout << "inf\n"; } else { std::cout << max << "\n"; } } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }