結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
![]() |
提出日時 | 2017-06-11 10:20:07 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,476 bytes |
コンパイル時間 | 785 ms |
コンパイル使用メモリ | 77,108 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-24 16:03:36 |
合計ジャッジ時間 | 2,216 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <algorithm> #include <iomanip> #include <istream> #include <map> #include <numeric> #include <ostream> #include <set> #include <sstream> #include <string> #include <utility> #include <vector> #include <cstring> #define MAX_N 100 using namespace std; const int M = 1000000007; int n; int w[MAX_N + 2], v[MAX_N + 2]; int dp[100000 + 2]; int V; class Solution { public: void solve(std::istream& in, std::ostream& out) { memset(dp, 0, sizeof(dp)); in >> n; for (int i = 0; i < n; i++) { in >> v[i] >> w[i]; } in >> V; fill(dp + 1, dp + 100001, M); for (int i = 0; i < n; i++) { for (int j = 100000; j > 0 ; j--) { if (j <= v[i]) { dp[j] = min(dp[j], w[i]); } else { dp[j] = min(dp[j], dp[j - v[i]] + w[i]); } } } out << max(dp[V], 1) << endl; stringstream ss; ss << dp[V + 1] - 1; out << (dp[V + 1] < M ? ss.str() : "inf") << endl; } }; void solve(std::istream& in, std::ostream& out) { out << std::setprecision(12); Solution solution; solution.solve(in, out); } #include <fstream> #include <iostream> int main() { ios_base::sync_with_stdio(0); cin.tie(0); istream& in = cin; ostream& out = cout; solve(in, out); return 0; }