結果
問題 | 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 1000000007using 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 LOCALifstream in("input.txt");cin.rdbuf(in.rdbuf());#endifcin >> 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;}