結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2018-09-09 06:44:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 1,127 bytes |
コンパイル時間 | 1,786 ms |
コンパイル使用メモリ | 168,068 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-23 02:41:37 |
合計ジャッジ時間 | 3,640 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using int64 = long long; using uint64 = unsigned long long; constexpr int MAX_CAP = 100000; int table[MAX_CAP + 10]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; memset(table, -1, sizeof(table)); table[0] = 0; int wsum = 0; for (int i = 0; i < N; i++) { int v, w; cin >> v >> w; wsum += w; for (int cap = MAX_CAP; cap > 0; cap--) { if (cap - w >= 0 and table[cap - w] >= 0) { table[cap] = max(table[cap], table[cap - w] + v); } } } for (int cap = 0; cap <= wsum; cap++) { table[cap + 1] = max(table[cap + 1], table[cap]); } int V; cin >> V; int capMin = wsum, capMax = 0; for (int cap = 1; cap <= wsum; cap++) { if (table[cap] == V) { capMin = min(capMin, cap); capMax = max(capMax, cap); } } cout << capMin << endl; cout << (capMax == wsum ? "inf" : to_string(capMax)) << endl; return 0; }