結果
問題 | No.527 ナップサック容量問題 |
ユーザー |
|
提出日時 | 2017-06-09 22:57:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 2,193 bytes |
コンパイル時間 | 1,628 ms |
コンパイル使用メモリ | 167,792 KB |
実行使用メモリ | 81,620 KB |
最終ジャッジ日時 | 2024-09-22 16:43:13 |
合計ジャッジ時間 | 3,547 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;using i32 = int; using i64 = long long int; using f64 = double; using str = string;template <typename T> using vec = vector<T>;template <typename T> using heap = priority_queue<T>;void in() {}; template <typename T, typename...TS> void in(T &&x, TS &&...xs) { cin>>x; in(move(xs)...); };template <typename T> void _out(const char *sep, const char *end, T &&x) { cout<<x<<end; };template <typename T, typename...TS> void _out(const char *sep, const char *end, T &&x, TS &&...xs) { cout<<x<<sep; _out(sep, end, move(xs)...); }#define indef(t, ...) t __VA_ARGS__; in(__VA_ARGS__)#define get(t) []{ t _; cin >> _; return _; }()#define put(...) _out("", "", __VA_ARGS__)#define out(...) _out(" ", "\n", __VA_ARGS__)#define times(n, i) for (i32 i = 0 ; i < (n); ++i)#define range(a, b, i) for (i32 i = (a); i < (b); ++i)#define upto(a, b, i) for (i32 i = (a); i <= (b); ++i)#define downto(a, b, i) for (i32 i = (a); i >= (b); --i)#define all(xs) (xs).begin(), (xs).end()#define sortall(xs) sort(all(xs))#define reverseall(xs) reverse(all(xs))#define even(x) (((x) & 1) == 0)#define odd(x) (((x) & 1) == 1)#define append emplace_back#define findge lower_bound#define findgt upper_boundconst i64 MOD = 1000000007;const f64 EPS = 1e-10;i64 n, m;i64 v[100], w[100];i64 dp[101][100001];i32 main(){in(n);i64 allw = 0;times(n, i) {in(v[i], w[i]);allw += w[i];}in(m);upto(1, 100000, wi) {upto(1, n, ni) {if (wi >= w[ni-1]) {dp[ni][wi] = max(dp[ni-1][wi], dp[ni-1][wi-w[ni-1]] + v[ni-1]);}else {dp[ni][wi] = dp[ni-1][wi];}}}i64 low = 0, high = 0;upto(1, allw, wi) {if (dp[n][wi] == m) {low = wi;break;}}upto(low+1, allw, wi) {if (dp[n][wi] != m) {high = wi-1;break;}}out(low);if (high < low || high == allw) {out("inf");}else {out(high);}return 0;}