結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
![]() |
提出日時 | 2017-06-09 23:27:24 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 823 bytes |
コンパイル時間 | 529 ms |
コンパイル使用メモリ | 37,120 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-22 19:13:51 |
合計ジャッジ時間 | 1,538 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:31:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 31 | scanf("%d%d", &bv, &bw); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:39:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 39 | scanf("%d", &v); | ~~~~~^~~~~~~~~~
ソースコード
#include<cstdio>#include<vector>using namespace std;using vi=vector<int>;void max_u(int&m, int v){if(m<v){m=v;}}int main(void){int n, v;while(scanf("%d", &n)==1){vi dp;int bv, bw, bw_sum=0;dp.assign(100000+1, -1);dp[0]=0;for(int i=0;i<n;i++){scanf("%d%d", &bv, &bw);bw_sum+=bw;for(int j=100000-bw;j>=0;j--){if(dp[j]<0) continue;max_u(dp[j+bw], dp[j]+bv);}}scanf("%d", &v);for(int i=1;i<=100000;i++){max_u(dp[i], dp[i-1]);}int ans_min=-1, ans_max=100000+1;for(int i=1;i<=100000;i++){if(dp[i]==v){if(ans_min<0) ans_min=i;ans_max=i;}}if(ans_min<0) ans_min=1;printf("%d\n", ans_min);if(bw_sum<100000 && dp[bw_sum]==v) printf("inf\n");else printf("%d\n", ans_max);}return 0;}