結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2019-08-01 18:33:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 2,034 bytes |
コンパイル時間 | 756 ms |
コンパイル使用メモリ | 98,036 KB |
実行使用メモリ | 81,536 KB |
最終ジャッジ日時 | 2024-07-05 07:46:26 |
合計ジャッジ時間 | 2,547 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
//#pragma GCC optimize ("-O3","unroll-loops") #include<iostream> #include<string> #include<algorithm> #include<vector> #include<queue> #include<map> #include<math.h> #include<iomanip> #include<set> #include<numeric> #include<cstring> #include<cstdio> #include<functional> #include<bitset> #include<limits.h> #include<cassert> #include<iterator> #include<complex> #include<stack> #include <stdio.h> #define REP(i, n) for(int i = 0;i < n;i++) #define REPR(i, n) for(int i = n;i >= 0;i--) #define FOR(i, m, n) for(int i = m;i < n;i++) #define FORR(i, m, n) for(int i = m;i >= n;i--) #define SORT(v, n) sort(v, v+n); #define VSORT(v) sort(v.begin(), v.end()); #define REVERSE(v,n) reverse(v,v+n); #define VREVERSE(v) reverse(v.begin(), v.end()); #define ll long long #define pb(a) push_back(a) #define m0(x) memset(x,0,sizeof(x)) #define print(x) cout<<x<<'\n'; #define pe(x) cout<<x<<" "; #define lb(v,n) lower_bound(v.begin(), v.end(), n); #define ub(v,n) upper_bound(v.begin(), v.end(), n); #define int long long #define all(x) (x).begin(), (x).end() //#define double long double using namespace std; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } const int MOD = 1e9 + 7; const ll INF = 1e17; const double pi = acos(-1); const double EPS = 1e-10; typedef pair<int, int>P; const int MAX = 200020; int dp[110][100010]; int v[110], w[110], N, V; signed main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; int sum = 0; REP(i, N) { cin >> v[i] >> w[i]; sum += v[i]; } cin >> V; REP(i, N) { REP(j, 100001) { if (j >= w[i]) { dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]); } else { dp[i + 1][j] = dp[i][j]; } } } int mn = INF, mx = -INF; FOR(j,1, 100001) { if (dp[N][j] == V) { chmin(mn, j); chmax(mx, j); } } if (sum == V)mx = -1; print(mn); if (mx == -1) { print("inf"); } else print(mx); }