# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1221101 | longgggg | Knapsack (NOI18_knapsack) | C++17 | 1097 ms | 8624 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#pragma O3
#define IN "A.in"
#define OUT "A.out"
#define DEBUG "debug.out"
const int mxN = 100005, INF = (int) 1e9+5;
const ll MOD = (ll) 1e9+7, LINF = (ll) 1e18;
void solve() {
int n, limit; cin >> limit >> n;
// Binary Decomposition
vector <pair <int, int>> items; // (w, v)
for (int i = 1; i <= n; i++) {
int v, w, k; cin >> v >> w >> k;
int mx = min(k, limit / w);
for (ll curr_copy = 1; mx > 0; curr_copy <<= 1) {
int use = min((ll)mx, curr_copy);
items.push_back({w * use, v * use});
mx -= use;
}
}
// for (auto &x : items) cerr << x.first << " " << x.second << endl;
vector <ll> dp(limit + 1, 0);
for (auto &it : items) {
int w = it.first, v = it.second;
for (int j = limit; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[limit] << endl;
}
signed main() {
if (fopen(IN, "r")) {
freopen(IN, "r", stdin);
freopen(OUT, "w", stdout);
freopen(DEBUG, "w", stderr);
}
ios_base::sync_with_stdio(0); cin.tie(0);
clock_t start = clock();
// ll t; cin >> t;
// while (t--)
solve();
cerr << "Time: " << clock() - start << "ms\n";
}
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... |