# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
957560 | 2024-04-04T03:23:21 Z | roadster | Knapsack (NOI18_knapsack) | C++17 | 2 ms | 1368 KB |
#include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vector<int> >; using pi = pair<int, int>; using ll = long long; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define f first #define s second #define pb push_back const ll MOD = 1e9 + 7; ll expo(ll x, ll n) { ll res = 1LL; while (n) { if (n % 2){ res = res * x % MOD; } x = x * x % MOD; n /= 2; } return res; } vector<ll> factorial(int n) { vector<ll> fact(n + 1); fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = fact[i - 1] * i % MOD; } return fact; } vector<ll> mod_inverse(int n, ll fact_n) { vector<ll> inv(n + 1); inv[n] = expo(fact_n, MOD - 2); for (int i = n; i >= 1; i--) { inv[i - 1] = inv[i] * i % MOD; } return inv; } void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // your code goes here int t, n; cin >> t >> n; vi v(n + 1), w(n + 1), k(n + 1); for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> k[i]; vvi dp(n + 1, vi (t + 1)); for (int i = 1; i <= n; i++) { vi used(t + 1); for (int j = 1; j <= t; j++) { int a = INT_MIN, b = INT_MIN, c = INT_MIN; a = dp[i-1][j]; if (j - w[i] >= 0) { b = dp[i-1][j-w[i]] + v[i]; if (used[j-w[i]] < k[i]) c = dp[i][j-w[i]] + v[i]; } int res = max({a, b, c}); if (res == a) { dp[i][j] = res; } else if (res == b) { dp[i][j] = res; used[j] = 1; } else if (res == c) { dp[i][j] = res; used[j] = used[j-w[i]] + 1; } } } int ans = 0; for (int i = 1; i <= t; i++) ans = max(ans, dp[n][i]); cout << ans << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 1116 KB | Output is correct |
3 | Correct | 1 ms | 1116 KB | Output is correct |
4 | Correct | 1 ms | 1116 KB | Output is correct |
5 | Correct | 1 ms | 1368 KB | Output is correct |
6 | Correct | 2 ms | 1116 KB | Output is correct |
7 | Correct | 1 ms | 1116 KB | Output is correct |
8 | Correct | 2 ms | 1116 KB | Output is correct |
9 | Correct | 1 ms | 1116 KB | Output is correct |
10 | Correct | 1 ms | 1116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 1116 KB | Output is correct |
3 | Correct | 1 ms | 1116 KB | Output is correct |
4 | Correct | 1 ms | 1116 KB | Output is correct |
5 | Correct | 1 ms | 1368 KB | Output is correct |
6 | Correct | 2 ms | 1116 KB | Output is correct |
7 | Correct | 1 ms | 1116 KB | Output is correct |
8 | Correct | 2 ms | 1116 KB | Output is correct |
9 | Correct | 1 ms | 1116 KB | Output is correct |
10 | Correct | 1 ms | 1116 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Incorrect | 1 ms | 1116 KB | Output isn't correct |
13 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 1116 KB | Output is correct |
7 | Correct | 1 ms | 1116 KB | Output is correct |
8 | Correct | 1 ms | 1116 KB | Output is correct |
9 | Correct | 1 ms | 1368 KB | Output is correct |
10 | Correct | 2 ms | 1116 KB | Output is correct |
11 | Correct | 1 ms | 1116 KB | Output is correct |
12 | Correct | 2 ms | 1116 KB | Output is correct |
13 | Correct | 1 ms | 1116 KB | Output is correct |
14 | Correct | 1 ms | 1116 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Incorrect | 1 ms | 1116 KB | Output isn't correct |
17 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 1116 KB | Output is correct |
7 | Correct | 1 ms | 1116 KB | Output is correct |
8 | Correct | 1 ms | 1116 KB | Output is correct |
9 | Correct | 1 ms | 1368 KB | Output is correct |
10 | Correct | 2 ms | 1116 KB | Output is correct |
11 | Correct | 1 ms | 1116 KB | Output is correct |
12 | Correct | 2 ms | 1116 KB | Output is correct |
13 | Correct | 1 ms | 1116 KB | Output is correct |
14 | Correct | 1 ms | 1116 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Incorrect | 1 ms | 1116 KB | Output isn't correct |
17 | Halted | 0 ms | 0 KB | - |