結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
|
提出日時 | 2017-07-19 21:06:40 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 1,258 bytes |
コンパイル時間 | 796 ms |
コンパイル使用メモリ | 87,340 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-08 14:31:33 |
合計ジャッジ時間 | 2,089 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> using namespace std; #define ALL(g) (g).begin(),(g).end() #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define F(i,j,k) fill(i[0],i[0]+j*j,k) #define P(p) cout<<(p)<<endl; #define EXIST(s,e) ((s).find(e)!=(s).end()) #define INF 1<<25 #define pb push_back typedef vector<int> vi; typedef vector<long long> vl; typedef vector<double> vd; typedef pair<int,int> pii; typedef pair<long,long> pll; typedef long long ll; int v[101],w[101],dp[100001];//重さのMAX価値を保存 int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>v[i]>>w[i]; for(int j=100000;j>=0;j--){ dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i]); } } int max_v,mn=100001,mx=0; cin>>max_v; for(int i=0;i<=100001;i++){ if(dp[i]==max_v){ mn=min(mn,i); mx=max(mx,i); } } if(mx==100001){ cout<<max(mn,1)<<endl; cout<<"inf\n"; } else{ cout<<max(mn,1)<<endl; cout<<mx<<endl; } }