結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
![]() |
提出日時 | 2017-06-09 23:03:54 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,036 ms / 2,000 ms |
コード長 | 1,572 bytes |
コンパイル時間 | 871 ms |
コンパイル使用メモリ | 80,312 KB |
実行使用メモリ | 46,464 KB |
最終ジャッジ日時 | 2024-09-22 17:04:10 |
合計ジャッジ時間 | 15,594 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
//#define LOCAL #include <fstream> #include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <queue> #include <cstring> #include <climits> #include <set> //#define int long long //typedef long long ll; using ll = long long; using R = double; //#define rep(i,n) for(int i=0; i<(n); i++) #define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++) #define REP(i,n) FOR(i,0,n) #define MOD 1000000007 using namespace std; //typedef vector<int> V; //typedef vector<V> VV; int N; int v[110], w[110]; int V; int dp[110][100010]; int rec(int i, int j) { if (dp[i][j] >= 0) { return dp[i][j]; } int res; if (i == N) { res = 0; } else if (j < w[i]) { res = rec(i + 1, j); } else { res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]); } return dp[i][j] = res; } signed main() { #ifdef LOCAL ifstream in("input.txt"); cin.rdbuf(in.rdbuf()); #endif cin >> N; REP(i,N) cin >> v[i] >> w[i]; cin >> V; //最小値 int lb = 0, ub = 100010; while (ub - lb > 1) { int mid = (lb + ub) / 2; memset(dp, -1, sizeof(dp)); if (rec(0, mid) >= V) ub = mid; else lb = mid; } cout << ub << endl; //最大値 lb = 0, ub = 100010; while (ub - lb > 1) { int mid = (lb + ub) / 2; memset(dp, -1, sizeof(dp)); if (rec(0, mid) <= V) lb = mid; else ub = mid; } if (lb > 100005) { cout << "inf" << endl; } else { cout << lb << endl; } return 0; }