結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2017-06-10 22:02:55 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 1,249 bytes |
コンパイル時間 | 600 ms |
コンパイル使用メモリ | 87,056 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 15:46:15 |
合計ジャッジ時間 | 1,766 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:38:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | scanf("%d",&n); | ~~~~~^~~~~~~~~ main.cpp:41:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 41 | scanf("%d%d",v+i,w+i); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:45:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 45 | scanf("%d",&V); | ~~~~~^~~~~~~~~
ソースコード
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <functional> #include <cassert> typedef long long ll; using namespace std; #define debug(x) cerr << #x << " = " << (x) << endl; #define mod 1000000007 //1e9+7(prime number) #define INF 1000000000 //1e9 #define LLINF 2000000000000000000LL //2e18 #define SIZE 100010 int dp[SIZE]; int main(){ int n,V,sum = 0; int v[SIZE], w[SIZE]; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",v+i,w+i); sum += w[i]; } scanf("%d",&V); for(int j=0;j<=sum+1;j++){ dp[j] = -INF; } dp[0] = 0; for(int i=0;i<n;i++){ for(int j=sum-w[i];j>=0;j--){ dp[j+w[i]] = max(dp[j+w[i]], dp[j] + v[i]); } } int ans_min = INF, ans_max = -1; for(int i=0;i<=sum;i++){ dp[i+1] = max(dp[i+1], dp[i]); if(dp[i] == V){ ans_min = min(ans_min, i); ans_max = max(ans_max, i); } } if(dp[sum] != V) printf("%d\n%d\n",max(1,ans_min), ans_max); else printf("%d\ninf\n",ans_min); return 0; }