# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1265584 | tochika | Knapsack (NOI18_knapsack) | C++20 | 1096 ms | 1600 KiB |
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
#define IN "iii.txt"
#define OUT "ooo.txt"
#define MULTI_TEST 0
const int MOD = 1e9 + 7;
const int MAX = 1e8 + 5;
const lint LMAX = 1e18;
void solve() {
int s, n;
cin >> s >> n;
vector<vector<pair<int, int>>> grouped(s + 1);
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
if (w > s)
continue;
grouped[w].push_back({v, k});
}
vector<lint> dp(s + 1, 0);
for (int w = 1; w <= s; w++) {
if (grouped[w].empty())
continue;
for (auto items : grouped[w]) {
int v = items.first;
int k = items.second;
for (int rem = 0; rem < w; rem++) {
deque<pair<int, lint>> dq;
int max_i = (s - rem) / w;
for (int i = 0; i <= max_i; i++) {
int c = rem + i * w;
lint base = dp[c] - (lint)i * v;
while (!dq.empty() && dq.back().second <= base)
dq.pop_back();
dq.push_back({i, base});
if (dq.front().first < i - k)
dq.pop_front();
if (!dq.empty()) {
lint best = dq.front().second;
lint new_total = best +(lint)i * v;
dp[c] = max(dp[c], new_total);
}
}
}
}
}
cout << *max_element(dp.begin(), dp.end());
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(IN, "r")) {
freopen(IN, "r", stdin);
freopen(OUT, "w", stdout);
}
int t = 1;
if (MULTI_TEST) {
cin >> t;
}
for (int i = 1; i <= t; i++) {
solve();
cout << '\n';
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |