結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
![]() |
提出日時 | 2017-06-09 23:15:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 614 bytes |
コンパイル時間 | 740 ms |
コンパイル使用メモリ | 65,700 KB |
実行使用メモリ | 42,944 KB |
最終ジャッジ日時 | 2024-09-22 18:24:29 |
合計ジャッジ時間 | 2,193 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <iostream>using namespace std;int main(){int n, V;cin >> n;int v[n], w[n];for(int i = 0; i < n; i++) cin >> v[i] >> w[i];cin >> V;int dp[n + 1][100001]{};for(int i = 0; i < n; i++) for(int j = 0; j < 100001; j++){dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);if(j + w[i] < 100001){dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);}}int l = -1, r = -1;for(int i = 1; i < 100001; i++) if(dp[n][i] == V){((l == -1) ? l : r) = i;}if(r == -1) r = l;if(r == 100000){cout << l << endl << "inf" << endl;return 0;}cout << l << endl << r << endl;}