# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1265597 | tochika | Knapsack (NOI18_knapsack) | C++20 | 34 ms | 1608 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;
vector<int> best_w;
int limit = s / w;
sort(grouped[w].begin(), grouped[w].end(), [](pair<int, int>& a, pair<int, int>& b){
return a.first > b.first;
});
for (auto items : grouped[w]) {
int v = items.first;
int k = items.second;
for (int i = 0; i < k; i++) {
if (best_w.size() >= limit)
break;
best_w.push_back(v);
}
if (best_w.size() >= limit)
break;
}
for (int v_val : best_w) {
for (int c = s; c >= w; c--) {
dp[c] = max(dp[c], dp[c - w] + v_val);
}
}
}
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... |