結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2022-10-27 16:49:51 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 338 ms / 2,000 ms |
コード長 | 1,273 bytes |
コンパイル時間 | 1,507 ms |
コンパイル使用メモリ | 143,336 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-05 02:10:15 |
合計ジャッジ時間 | 4,977 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; int N; vector<int> V; vector<int> W; int solve(int lim) { int dp[lim + 1]; memset(dp, -1, sizeof(dp)); dp[0] = 0; int ans = 0; for (int i = 0; i < N; ++i) { int v = V[i]; int w = W[i]; for (int j = lim - w; j >= 0; --j) { if (dp[j] == -1) continue; int nj = j + w; dp[nj] = max(dp[nj], dp[j] + v); ans = max(ans, dp[nj]); } } return ans; } int main() { cin >> N; V.resize(N); W.resize(N); for (int i = 0; i < N; ++i) { cin >> V[i] >> W[i]; } int V; cin >> V; int ng = 0; int ok = 200000; while (abs(ok - ng) >= 2) { int x = (ok + ng) / 2; int v = solve(x); if (v >= V) { ok = x; } else { ng = x; } } cout << ok << endl; ng = 0; ok = 200000; while (abs(ok - ng) >= 2) { int x = (ok + ng) / 2; int v = solve(x); if (v > V) { ok = x; } else { ng = x; } } if (ok <= 100000) { cout << ok - 1 << endl; } else { cout << "inf" << endl; } return 0; }