# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
541301 | 2022-03-23T01:05:32 Z | eulerdesoja | Knapsack (NOI18_knapsack) | C++17 | 217 ms | 35216 KB |
#include <bits/stdc++.h> using namespace std; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); freopen((s+ ".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } #define int long long #define pb push_back #define sz(x) (int)x.size() #define endl "\n" typedef pair<int,int>ii; typedef vector<int> vi; const int mxn = 2e3 + 5; int dp[mxn][mxn], s, n; vector<ii> p[mxn]; int cnt(int i, int cap) { if (i == s + 1 || cap == 0) return 0; int &ans = dp[i][cap]; if (ans != -1)return ans; int w_sum = 0, v_sum = 0; ans = 0; ans = max(ans, cnt(i + 1, cap)); for (ii cur: p[i]) { if (w_sum + i > cap)break; int qtd = cur.second; while(qtd-- && w_sum + i <= cap) { w_sum += i; v_sum += cur.first; //cout<<i<<" "<<w_sum<<" "<<v_sum<<"\n"; ans = max(ans, cnt(i + 1, cap - w_sum) + v_sum); } } return ans; } void solve() { cin>>s>>n; for (int i = 0; i < n; i++) { int v, w, k;cin>>v>>w>>k; p[w].pb({v, k}); } for (int i = 0; i < mxn; i++)sort(p[i].begin(), p[i].end(), greater<ii>()); // for (int i = 0; i < mxn;i++)if(sz(p[i])) { // for (ii j: p[i])cout<<j.first<<" "<<j.second<<" "; // cout<<"\n"; // } memset(dp, -1, sizeof(dp)); cout<<cnt(1, s)<<"\n"; } int32_t main(void) { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); //setIO("convention"); int t = 1; //cin>>t; while(t--) solve(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 31956 KB | Output is correct |
2 | Correct | 14 ms | 31864 KB | Output is correct |
3 | Correct | 16 ms | 31956 KB | Output is correct |
4 | Correct | 14 ms | 31876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 31828 KB | Output is correct |
2 | Correct | 16 ms | 32024 KB | Output is correct |
3 | Correct | 18 ms | 31996 KB | Output is correct |
4 | Correct | 13 ms | 31968 KB | Output is correct |
5 | Correct | 13 ms | 32008 KB | Output is correct |
6 | Correct | 83 ms | 32072 KB | Output is correct |
7 | Correct | 87 ms | 32064 KB | Output is correct |
8 | Correct | 81 ms | 32064 KB | Output is correct |
9 | Correct | 91 ms | 32068 KB | Output is correct |
10 | Correct | 82 ms | 32068 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 31828 KB | Output is correct |
2 | Correct | 16 ms | 32024 KB | Output is correct |
3 | Correct | 18 ms | 31996 KB | Output is correct |
4 | Correct | 13 ms | 31968 KB | Output is correct |
5 | Correct | 13 ms | 32008 KB | Output is correct |
6 | Correct | 83 ms | 32072 KB | Output is correct |
7 | Correct | 87 ms | 32064 KB | Output is correct |
8 | Correct | 81 ms | 32064 KB | Output is correct |
9 | Correct | 91 ms | 32068 KB | Output is correct |
10 | Correct | 82 ms | 32068 KB | Output is correct |
11 | Correct | 12 ms | 31828 KB | Output is correct |
12 | Correct | 56 ms | 32084 KB | Output is correct |
13 | Correct | 19 ms | 31992 KB | Output is correct |
14 | Correct | 12 ms | 32084 KB | Output is correct |
15 | Correct | 12 ms | 31992 KB | Output is correct |
16 | Correct | 106 ms | 32084 KB | Output is correct |
17 | Correct | 96 ms | 32084 KB | Output is correct |
18 | Correct | 89 ms | 32072 KB | Output is correct |
19 | Correct | 93 ms | 32084 KB | Output is correct |
20 | Correct | 118 ms | 32084 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 31956 KB | Output is correct |
2 | Correct | 14 ms | 31864 KB | Output is correct |
3 | Correct | 16 ms | 31956 KB | Output is correct |
4 | Correct | 14 ms | 31876 KB | Output is correct |
5 | Correct | 13 ms | 31828 KB | Output is correct |
6 | Correct | 16 ms | 32024 KB | Output is correct |
7 | Correct | 18 ms | 31996 KB | Output is correct |
8 | Correct | 13 ms | 31968 KB | Output is correct |
9 | Correct | 13 ms | 32008 KB | Output is correct |
10 | Correct | 83 ms | 32072 KB | Output is correct |
11 | Correct | 87 ms | 32064 KB | Output is correct |
12 | Correct | 81 ms | 32064 KB | Output is correct |
13 | Correct | 91 ms | 32068 KB | Output is correct |
14 | Correct | 82 ms | 32068 KB | Output is correct |
15 | Correct | 12 ms | 31828 KB | Output is correct |
16 | Correct | 56 ms | 32084 KB | Output is correct |
17 | Correct | 19 ms | 31992 KB | Output is correct |
18 | Correct | 12 ms | 32084 KB | Output is correct |
19 | Correct | 12 ms | 31992 KB | Output is correct |
20 | Correct | 106 ms | 32084 KB | Output is correct |
21 | Correct | 96 ms | 32084 KB | Output is correct |
22 | Correct | 89 ms | 32072 KB | Output is correct |
23 | Correct | 93 ms | 32084 KB | Output is correct |
24 | Correct | 118 ms | 32084 KB | Output is correct |
25 | Correct | 12 ms | 31828 KB | Output is correct |
26 | Correct | 107 ms | 32084 KB | Output is correct |
27 | Correct | 16 ms | 32084 KB | Output is correct |
28 | Correct | 13 ms | 31996 KB | Output is correct |
29 | Correct | 14 ms | 32084 KB | Output is correct |
30 | Correct | 99 ms | 32072 KB | Output is correct |
31 | Correct | 117 ms | 32088 KB | Output is correct |
32 | Correct | 100 ms | 32084 KB | Output is correct |
33 | Correct | 84 ms | 32044 KB | Output is correct |
34 | Correct | 90 ms | 32068 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 31956 KB | Output is correct |
2 | Correct | 14 ms | 31864 KB | Output is correct |
3 | Correct | 16 ms | 31956 KB | Output is correct |
4 | Correct | 14 ms | 31876 KB | Output is correct |
5 | Correct | 13 ms | 31828 KB | Output is correct |
6 | Correct | 16 ms | 32024 KB | Output is correct |
7 | Correct | 18 ms | 31996 KB | Output is correct |
8 | Correct | 13 ms | 31968 KB | Output is correct |
9 | Correct | 13 ms | 32008 KB | Output is correct |
10 | Correct | 83 ms | 32072 KB | Output is correct |
11 | Correct | 87 ms | 32064 KB | Output is correct |
12 | Correct | 81 ms | 32064 KB | Output is correct |
13 | Correct | 91 ms | 32068 KB | Output is correct |
14 | Correct | 82 ms | 32068 KB | Output is correct |
15 | Correct | 12 ms | 31828 KB | Output is correct |
16 | Correct | 56 ms | 32084 KB | Output is correct |
17 | Correct | 19 ms | 31992 KB | Output is correct |
18 | Correct | 12 ms | 32084 KB | Output is correct |
19 | Correct | 12 ms | 31992 KB | Output is correct |
20 | Correct | 106 ms | 32084 KB | Output is correct |
21 | Correct | 96 ms | 32084 KB | Output is correct |
22 | Correct | 89 ms | 32072 KB | Output is correct |
23 | Correct | 93 ms | 32084 KB | Output is correct |
24 | Correct | 118 ms | 32084 KB | Output is correct |
25 | Correct | 12 ms | 31828 KB | Output is correct |
26 | Correct | 107 ms | 32084 KB | Output is correct |
27 | Correct | 16 ms | 32084 KB | Output is correct |
28 | Correct | 13 ms | 31996 KB | Output is correct |
29 | Correct | 14 ms | 32084 KB | Output is correct |
30 | Correct | 99 ms | 32072 KB | Output is correct |
31 | Correct | 117 ms | 32088 KB | Output is correct |
32 | Correct | 100 ms | 32084 KB | Output is correct |
33 | Correct | 84 ms | 32044 KB | Output is correct |
34 | Correct | 90 ms | 32068 KB | Output is correct |
35 | Correct | 40 ms | 34096 KB | Output is correct |
36 | Correct | 127 ms | 34280 KB | Output is correct |
37 | Correct | 123 ms | 34284 KB | Output is correct |
38 | Correct | 42 ms | 34604 KB | Output is correct |
39 | Correct | 49 ms | 34476 KB | Output is correct |
40 | Correct | 196 ms | 34960 KB | Output is correct |
41 | Correct | 217 ms | 34972 KB | Output is correct |
42 | Correct | 210 ms | 34976 KB | Output is correct |
43 | Correct | 193 ms | 34988 KB | Output is correct |
44 | Correct | 209 ms | 34972 KB | Output is correct |
45 | Correct | 162 ms | 34980 KB | Output is correct |
46 | Correct | 49 ms | 34440 KB | Output is correct |
47 | Correct | 148 ms | 35216 KB | Output is correct |
48 | Correct | 157 ms | 34908 KB | Output is correct |
49 | Correct | 44 ms | 34952 KB | Output is correct |
50 | Correct | 174 ms | 34604 KB | Output is correct |