結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
![]() |
提出日時 | 2017-06-10 06:32:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 208 ms / 2,000 ms |
コード長 | 1,470 bytes |
コンパイル時間 | 1,693 ms |
コンパイル使用メモリ | 169,376 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-24 15:26:15 |
合計ジャッジ時間 | 4,229 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; #define INF 100002 int N; int v[105]; int w[105]; int V; bool C(int W){ vector<int> dp(W+1, -1); dp[0] = 0; rep(i,N){ for(int j=W; j>=0; j--){ if(dp[j]>=0 && j+w[i]<=W){ dp[j+w[i]] = max(dp[j+w[i]], dp[j] + v[i]); } } } int ret = 0; rep(i,dp.size()){ ret = max(ret, dp[i]); } return ret < V; } bool C2(int W){ vector<int> dp(W+1, -1); dp[0] = 0; rep(i,N){ for(int j=W; j>=0; j--){ if(dp[j]>=0 && j+w[i]<=W){ dp[j+w[i]] = max(dp[j+w[i]], dp[j] + v[i]); } } } int ret = 0; rep(i,dp.size()){ ret = max(ret, dp[i]); } return ret == V; } int main(){ cin >> N; rep(i,N){ cin >> v[i] >> w[i]; } cin >> V; int ret_min, ret_max; { int lb = 0, ub = INF; while(ub-lb>1){ int m = (lb+ub)/2; if(C(m)) lb = m; else ub = m; } ret_min = ub; } { int lb = ret_min, ub = INF; while(ub-lb>1){ int m = (lb+ub)/2; if(C2(m)) lb = m; else ub = m; } ret_max = lb; } cout << ret_min << endl; if(ret_max > 100000){ cout << "inf" << endl; }else{ cout << ret_max << endl; } return 0; }