# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
890586 | 2023-12-21T14:03:42 Z | Flan312 | Knapsack (NOI18_knapsack) | C++17 | 35 ms | 6100 KB |
#include <bits/stdc++.h> #define ll long long #define ld long double #define eb emplace_back #define task "" #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout); #define fi first #define se second #define pii pair <ll, ll> #define tii tuple <int, int, int> using namespace std; const int nmax = 1e5 + 2; int s, n, v[nmax], w[nmax], k[nmax]; int mxk = 0; void sub23() { vector<ll> dp(s + 1, 0); for (int i = 1; i <= n; ++i) for (int j = s; j >= w[i]; --j) for (int use = k[i]; use >= 0; --use) if (j >= 1ll * w[i] * use) dp[j] = max(dp[j], dp[j - w[i] * use] + 1ll * v[i] * use); cout << dp[s]; exit(0); } void sub45() { vector <vector <pii>> lst; lst.resize(s + 2); for (int i = 1; i <= n; ++i) { k[i] = min(k[i], s / w[i]); lst[w[i]].eb(v[i], k[i]); } vector <pii> best; for (int i = 1; i <= s; ++i) { sort(lst[i].rbegin(), lst[i].rend()); ll need = s / i; for (auto &[val, cnt] : lst[i]) { cnt = min(cnt, need); int use = 1; for (; use <= cnt; use <<= 1) { best.eb(val * use, 1ll * i * use); cnt -= use; need -= use; } if (need && cnt) { best.eb(val * cnt, 1ll * i * cnt); need -= cnt; cnt = 0; } } } vector <ll> dp(s + 2, 0); for (auto &[val, weight] : best) for (int j = s; j >= weight; --j) dp[j] = max(dp[j], dp[j - weight] + val); cout << dp[s]; exit(0); } int main() { if (ifstream(task".inp")) nx fast cin >> s >> n; for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> k[i], mxk = max(mxk, k[i]); if (n == 1) return cout << 1ll * v[1] * min(s / w[1], k[1]), 0; if (n <= 100 && mxk <= 10) sub23(); sub45(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 3 ms | 484 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 1 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 348 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 3 ms | 484 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
21 | Correct | 1 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 348 KB | Output is correct |
23 | Correct | 1 ms | 348 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 1 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 1 ms | 344 KB | Output is correct |
28 | Correct | 1 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 1 ms | 348 KB | Output is correct |
31 | Correct | 1 ms | 348 KB | Output is correct |
32 | Correct | 1 ms | 348 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 3 ms | 484 KB | Output is correct |
17 | Correct | 1 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
21 | Correct | 1 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 348 KB | Output is correct |
23 | Correct | 1 ms | 348 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 1 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 1 ms | 344 KB | Output is correct |
28 | Correct | 1 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 1 ms | 348 KB | Output is correct |
31 | Correct | 1 ms | 348 KB | Output is correct |
32 | Correct | 1 ms | 348 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 0 ms | 348 KB | Output is correct |
35 | Correct | 23 ms | 4588 KB | Output is correct |
36 | Correct | 24 ms | 5064 KB | Output is correct |
37 | Correct | 27 ms | 4816 KB | Output is correct |
38 | Correct | 24 ms | 5056 KB | Output is correct |
39 | Correct | 27 ms | 5460 KB | Output is correct |
40 | Correct | 29 ms | 5968 KB | Output is correct |
41 | Correct | 34 ms | 5464 KB | Output is correct |
42 | Correct | 35 ms | 5468 KB | Output is correct |
43 | Correct | 29 ms | 5460 KB | Output is correct |
44 | Correct | 27 ms | 5456 KB | Output is correct |
45 | Correct | 26 ms | 5860 KB | Output is correct |
46 | Correct | 21 ms | 5596 KB | Output is correct |
47 | Correct | 26 ms | 6100 KB | Output is correct |
48 | Correct | 27 ms | 5980 KB | Output is correct |
49 | Correct | 20 ms | 5724 KB | Output is correct |
50 | Correct | 25 ms | 5448 KB | Output is correct |