結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
|
提出日時 | 2019-09-22 22:54:31 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 209 ms / 2,000 ms |
コード長 | 1,025 bytes |
コンパイル時間 | 1,267 ms |
コンパイル使用メモリ | 165,008 KB |
実行使用メモリ | 18,272 KB |
最終ジャッジ日時 | 2024-09-19 03:46:42 |
合計ジャッジ時間 | 5,992 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long ll; ll N; int main(){ ll N; cin >> N; vector<pair<ll, ll > > vec; for(ll i = 0; i < N; i++){ ll v, w; cin >> v >> w; vec.push_back(make_pair(v, w)); } ll V; cin >> V; vector<ll > dp(1919191, 0); for(ll i = 0; i < N; i++){ for (ll j = dp.size() - 1; j >= 1 ; j--){ if(j - vec[i].second < 0){ break; } dp[j] = max(dp[j], dp[j - vec[i].second] + vec[i].first); } } ll max_w = 0; ll min_w = 0; for(ll i = 0; i < dp.size(); i++){ if(dp[i] == V && min_w == 0){ min_w = 1; if(i == 0){ cout << "1" << endl; }else{ cout << i << endl; } } if(dp[i] > V && max_w == 0){ max_w = 1; cout << i - 1 << endl; } } if(max_w == 0){ cout << "inf" << endl; } }