# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
983754 | 2024-05-16T04:33:43 Z | Peter2017 | Knapsack (NOI18_knapsack) | C++14 | 2 ms | 1884 KB |
#include <bits/stdc++.h> #define fi first #define se second #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define pill pair<int,ll> #define mem(a, b) memset(a, b, sizeof(a)) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define name "test" using namespace std; const int N = 1e5 + 5; const int S = 2e3 + 5; const int mod = 1e9 + 7; template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;} template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;} struct item{ int v, w, k; }; int n; int s; ll f[2][S]; item a[N]; ll Max[S]; deque<ll> dq[S]; void load(){ cin.tie(0)->sync_with_stdio(0); if (fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } } void input(){ cin >> s >> n; for (int i = 1; i <= n; i++) cin >> a[i].v >> a[i].w >> a[i].k; } void solve(){ for (int i = 1; i <= n; i++){ bool cur = (i & 1); bool pre = (cur ^ 1); for (int j = 0; j < a[i].w; j++){ while (dq[j].size()) dq[j].pop_back(); dq[j].push_back(j); } for (int j = a[i].w; j <= s; j++){ int p = j % a[i].w; while (dq[p].size() && (j - dq[p].front()) / a[i].w > a[i].k) dq[p].pop_front(); maxi(f[cur][j], f[pre][dq[p].back()] + ((j - dq[p].back()) / a[i].w) * a[i].v); maxi(f[cur][j], f[cur][j - 1]); while (dq[p].size()){ int id = dq[p].back(); if (f[pre][id] - ((id - p) / a[i].w) * a[i].v <= f[cur][j] - ((j - p) / a[i].w) * a[i].v) dq[p].pop_back(); else break; } dq[p].push_back(j); } } cout << f[n & 1][s]; } int main(){ load(); input(); solve(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 1884 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 1628 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 1628 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 1884 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 1884 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |