結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
![]() |
提出日時 | 2019-04-30 14:30:58 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,372 bytes |
コンパイル時間 | 928 ms |
コンパイル使用メモリ | 78,112 KB |
実行使用メモリ | 43,136 KB |
最終ジャッジ日時 | 2024-12-29 23:16:15 |
合計ジャッジ時間 | 3,156 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <string> #include <queue> #include <stack> #include <math.h> #include <set> #include <cstdio> #define ALL(obj) (obj).begin(),(obj).end() #define RALL(obj) (obj).rbegin(),(obj).rend() #define P pair<int, int> #define MOD 1000000007 #define INF 1012345678 #define NINF (-2147483647-1) #define LLINF 9223372036854775807 using ll = long long; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, V; cin >> N; vector<int> v(N), w(N); for (int i = 0; i < N; i++) { cin >> v[i] >> w[i]; } vector<vector<int>> dp(N + 1, vector<int>(1000 * N, 0)); for (int i = 1; i <= N; i++) { for (int j = 0; j < 1000 * N; j++) { if (j - w[i - 1] >= 0) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); } else { dp[i][j] = dp[i - 1][j]; } } } cin >> V; int ans = lower_bound(ALL(dp[N]), V) - dp[N].begin(); if (ans == 0) { cout << 1 << endl; } else { cout << ans << endl; } if (dp[N][1000 * N - 1] != V) { cout << upper_bound(ALL(dp[N]), V) - dp[N].begin() - 1 << endl; } else { cout << "inf" << endl; } getchar(); getchar(); }