# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

517020 | 2022-01-22T11:25:37 Z | DiTenix | Knapsack (NOI18_knapsack) | C++17 | 110 ms | 33024 KB |

#define eb emplace_back #define pb push_back #define pii pair<int,int> #define sz(x) int((x).size()) #define ALL(x) (x).begin(),(x).end() #define ln cout << '\n' #define REP(i, a) for (int i = 0; i < int(a); i++) #define FOR(i, a) for (int i = 1; i <= int(a); i++) #define MEM(a,b) memset((a),(b),sizeof(a)) const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; using namespace std; #include <bits/stdc++.h> using ll = long long; using vi = vector<int>; template<typename T> void rd(vector<T> &a) {for (auto &ele : a) cin >> ele;} template<typename T> void writeln(vector<T> &a) {for (auto &ele : a) cout << ele << ' '; cout << "\n";} #if __cplusplus > 201402L template<typename... Args> void rd(Args&... args) {((cin >> args), ...);} template<typename... Args> void write(Args... args) {((cout << args << " "), ...);} template<typename... Args> void writeln(Args... args) {((cout << args << " "), ...); cout << "\n";} #endif const int maxn = 1e6 + 5; ll v[maxn], w[maxn], k[maxn]; ll dp[2005][2005]; struct item { int v, k; }; vector<item> b[2005]; signed main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); // int t;cin >> t;while(t--) solve(); int n, S; cin >> S >> n; FOR(i, n) { int v, w, k; rd(v, w, k); b[w].pb({v, k}); } dp[0][0] = 0; int at = 0; for (int w = 1; w <= S; ++w) { if (b[w].empty()) continue; at++; sort(ALL(b[w]), [](item & a, item & b) { return a.v > b.v; }); auto& items = b[w]; for (int i = 0; i <= S; ++i) { dp[at][i] = dp[at - 1][i]; int copy = 0; int type_at = 0; int curr_used = 0; ll value = 0; while ((copy + 1) * w <= i && type_at < sz(items)) { copy++; value += items[type_at].v; dp[at][i] = max( dp[at][i], dp[at - 1][i - copy * w] + value ); curr_used++; if (curr_used == items[type_at].k) { curr_used = 0; type_at++; } } } } ll res = 0; for (int i = 0; i <= S; ++i) { res = max(res, dp[at][i]); } writeln(res); return 0; }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 332 KB | Output is correct |

2 | Correct | 1 ms | 380 KB | Output is correct |

3 | Correct | 1 ms | 332 KB | Output is correct |

4 | Correct | 0 ms | 332 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 332 KB | Output is correct |

2 | Correct | 1 ms | 332 KB | Output is correct |

3 | Correct | 1 ms | 332 KB | Output is correct |

4 | Correct | 1 ms | 332 KB | Output is correct |

5 | Correct | 1 ms | 332 KB | Output is correct |

6 | Correct | 2 ms | 1740 KB | Output is correct |

7 | Correct | 2 ms | 1868 KB | Output is correct |

8 | Correct | 2 ms | 1740 KB | Output is correct |

9 | Correct | 1 ms | 1740 KB | Output is correct |

10 | Correct | 2 ms | 1740 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 332 KB | Output is correct |

2 | Correct | 1 ms | 332 KB | Output is correct |

3 | Correct | 1 ms | 332 KB | Output is correct |

4 | Correct | 1 ms | 332 KB | Output is correct |

5 | Correct | 1 ms | 332 KB | Output is correct |

6 | Correct | 2 ms | 1740 KB | Output is correct |

7 | Correct | 2 ms | 1868 KB | Output is correct |

8 | Correct | 2 ms | 1740 KB | Output is correct |

9 | Correct | 1 ms | 1740 KB | Output is correct |

10 | Correct | 2 ms | 1740 KB | Output is correct |

11 | Correct | 1 ms | 332 KB | Output is correct |

12 | Correct | 5 ms | 332 KB | Output is correct |

13 | Correct | 1 ms | 332 KB | Output is correct |

14 | Correct | 0 ms | 332 KB | Output is correct |

15 | Correct | 1 ms | 332 KB | Output is correct |

16 | Correct | 2 ms | 1908 KB | Output is correct |

17 | Correct | 1 ms | 1740 KB | Output is correct |

18 | Correct | 2 ms | 1868 KB | Output is correct |

19 | Correct | 2 ms | 1740 KB | Output is correct |

20 | Correct | 3 ms | 1868 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 332 KB | Output is correct |

2 | Correct | 1 ms | 380 KB | Output is correct |

3 | Correct | 1 ms | 332 KB | Output is correct |

4 | Correct | 0 ms | 332 KB | Output is correct |

5 | Correct | 1 ms | 332 KB | Output is correct |

6 | Correct | 1 ms | 332 KB | Output is correct |

7 | Correct | 1 ms | 332 KB | Output is correct |

8 | Correct | 1 ms | 332 KB | Output is correct |

9 | Correct | 1 ms | 332 KB | Output is correct |

10 | Correct | 2 ms | 1740 KB | Output is correct |

11 | Correct | 2 ms | 1868 KB | Output is correct |

12 | Correct | 2 ms | 1740 KB | Output is correct |

13 | Correct | 1 ms | 1740 KB | Output is correct |

14 | Correct | 2 ms | 1740 KB | Output is correct |

15 | Correct | 1 ms | 332 KB | Output is correct |

16 | Correct | 5 ms | 332 KB | Output is correct |

17 | Correct | 1 ms | 332 KB | Output is correct |

18 | Correct | 0 ms | 332 KB | Output is correct |

19 | Correct | 1 ms | 332 KB | Output is correct |

20 | Correct | 2 ms | 1908 KB | Output is correct |

21 | Correct | 1 ms | 1740 KB | Output is correct |

22 | Correct | 2 ms | 1868 KB | Output is correct |

23 | Correct | 2 ms | 1740 KB | Output is correct |

24 | Correct | 3 ms | 1868 KB | Output is correct |

25 | Correct | 1 ms | 332 KB | Output is correct |

26 | Correct | 8 ms | 332 KB | Output is correct |

27 | Correct | 2 ms | 332 KB | Output is correct |

28 | Correct | 1 ms | 384 KB | Output is correct |

29 | Correct | 1 ms | 332 KB | Output is correct |

30 | Correct | 3 ms | 1868 KB | Output is correct |

31 | Correct | 2 ms | 1868 KB | Output is correct |

32 | Correct | 2 ms | 1740 KB | Output is correct |

33 | Correct | 2 ms | 1868 KB | Output is correct |

34 | Correct | 2 ms | 1740 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 332 KB | Output is correct |

2 | Correct | 1 ms | 380 KB | Output is correct |

3 | Correct | 1 ms | 332 KB | Output is correct |

4 | Correct | 0 ms | 332 KB | Output is correct |

5 | Correct | 1 ms | 332 KB | Output is correct |

6 | Correct | 1 ms | 332 KB | Output is correct |

7 | Correct | 1 ms | 332 KB | Output is correct |

8 | Correct | 1 ms | 332 KB | Output is correct |

9 | Correct | 1 ms | 332 KB | Output is correct |

10 | Correct | 2 ms | 1740 KB | Output is correct |

11 | Correct | 2 ms | 1868 KB | Output is correct |

12 | Correct | 2 ms | 1740 KB | Output is correct |

13 | Correct | 1 ms | 1740 KB | Output is correct |

14 | Correct | 2 ms | 1740 KB | Output is correct |

15 | Correct | 1 ms | 332 KB | Output is correct |

16 | Correct | 5 ms | 332 KB | Output is correct |

17 | Correct | 1 ms | 332 KB | Output is correct |

18 | Correct | 0 ms | 332 KB | Output is correct |

19 | Correct | 1 ms | 332 KB | Output is correct |

20 | Correct | 2 ms | 1908 KB | Output is correct |

21 | Correct | 1 ms | 1740 KB | Output is correct |

22 | Correct | 2 ms | 1868 KB | Output is correct |

23 | Correct | 2 ms | 1740 KB | Output is correct |

24 | Correct | 3 ms | 1868 KB | Output is correct |

25 | Correct | 1 ms | 332 KB | Output is correct |

26 | Correct | 8 ms | 332 KB | Output is correct |

27 | Correct | 2 ms | 332 KB | Output is correct |

28 | Correct | 1 ms | 384 KB | Output is correct |

29 | Correct | 1 ms | 332 KB | Output is correct |

30 | Correct | 3 ms | 1868 KB | Output is correct |

31 | Correct | 2 ms | 1868 KB | Output is correct |

32 | Correct | 2 ms | 1740 KB | Output is correct |

33 | Correct | 2 ms | 1868 KB | Output is correct |

34 | Correct | 2 ms | 1740 KB | Output is correct |

35 | Correct | 32 ms | 1484 KB | Output is correct |

36 | Correct | 34 ms | 1524 KB | Output is correct |

37 | Correct | 30 ms | 1484 KB | Output is correct |

38 | Correct | 28 ms | 1436 KB | Output is correct |

39 | Correct | 32 ms | 1364 KB | Output is correct |

40 | Correct | 110 ms | 32860 KB | Output is correct |

41 | Correct | 67 ms | 33024 KB | Output is correct |

42 | Correct | 68 ms | 32836 KB | Output is correct |

43 | Correct | 84 ms | 32836 KB | Output is correct |

44 | Correct | 94 ms | 32760 KB | Output is correct |

45 | Correct | 35 ms | 4760 KB | Output is correct |

46 | Correct | 32 ms | 1512 KB | Output is correct |

47 | Correct | 40 ms | 7928 KB | Output is correct |

48 | Correct | 58 ms | 17124 KB | Output is correct |

49 | Correct | 23 ms | 2156 KB | Output is correct |

50 | Correct | 61 ms | 2080 KB | Output is correct |