結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
|
提出日時 | 2017-06-09 23:45:54 |
言語 | C90 (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 635 bytes |
コンパイル時間 | 508 ms |
コンパイル使用メモリ | 21,760 KB |
実行使用メモリ | 79,684 KB |
最終ジャッジ日時 | 2024-09-22 19:25:51 |
合計ジャッジ時間 | 2,058 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.c: In function ‘main’: main.c:7:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 7 | scanf("%d",&n); | ^~~~~~~~~~~~~~ main.c:9:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 9 | scanf("%ld %ld",&v[i],&w[i]); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.c:11:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 11 | scanf("%ld",&V); | ^~~~~~~~~~~~~~~
ソースコード
#include<stdio.h>#define max(a,b) (((a)>(b))?(a):(b))long dp[100][100001],v[100],w[100];int main(int argc, char const *argv[]){int n,i,f=0;long V,j;scanf("%d",&n);for(i=0;i<n;i++){scanf("%ld %ld",&v[i],&w[i]);}scanf("%ld",&V);for(j=w[0];j<=100000;j++){dp[0][j]=v[0];}for(i=1;i<n;i++){for(j=0;j<=100000;j++){dp[i][j]=dp[i-1][j];if(j>=w[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);}}for(j=1;j<=100000;j++){if(f==0 && dp[n-1][j]==V){printf("%ld\n",j);f=1;}else if(f==1 && dp[n-1][j]>V){f=2;printf("%ld\n",j-1);break;}}if(f==1) printf("inf\n");return 0;}