結果
問題 |
No.527 ナップサック容量問題
|
ユーザー |
![]() |
提出日時 | 2018-10-19 08:57:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 1,287 bytes |
コンパイル時間 | 1,554 ms |
コンパイル使用メモリ | 166,340 KB |
実行使用メモリ | 83,328 KB |
最終ジャッジ日時 | 2024-11-15 19:18:38 |
合計ジャッジ時間 | 5,583 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i,s,n) for(int i = s;i<n;i++) #define repe(i,s,n) for(int i = s;i<=n;i++) #define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--) #define all(v) (v).begin(),(v).end() #define pb push_back #define fi first #define se second #define chmin(a,b) a=min((a),(b)) #define chmax(a,b) a=max((a),(b)) typedef long long ll; typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; typedef pair<pint,int> P1; typedef pair<int,pint> P2; typedef pair<pint,pint>PP; static const ll maxLL = (ll)1 << 62; const ll MOD=1000000007; const ll INF=1e18; int dx[]={0,0,1,-1}; int dy[]={-1,1,0,0}; int N; int v[101],w[101]; int V; int dp[101][101010]; signed main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>N; rep(i,0,N){ cin>>v[i]>>w[i]; } cin>>V; memset(dp,0,sizeof(dp)); rep(i,0,N)rep(j,0,100002){ chmax(dp[i+1][j],dp[i][j]); chmax(dp[i+1][j+w[i]],dp[i][j]+v[i]); } int minans=INF,maxans=-1; rep(j,1,100002)if(dp[N][j]==V){ chmin(minans,j); chmax(maxans,j); } cout<<minans<<"\n"; if(maxans==100001)cout<<"inf"<<"\n"; else cout<<maxans<<"\n"; //rep(j,0,N)cout<<dp[N][j]<<endl; return 0; }