Submission #1183016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183016		Trn115	Knapsack (NOI18_knapsack)	C++17	73 / 100	1096 ms	16800 KiB

knapsack

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second
#define all(v) v.begin(), v.end()

using namespace std;
using pii = pair<int, int>;

int s, n, m;
vector<pii> a; // {value, weight}
vector<int> dp;

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> s >> n;
    while (n--) {
        int v, w, k;
        cin >> v >> w >> k;
        int x = 1;
        while (x <= k) {
            if (w * x <= s) a.push_back({v * x, w * x});
            k -= x;
            x <<= 1;
        }
        a.push_back({v * k, w * k});
    }
    m = a.size(); a.insert(a.begin(), {0, 0});

    dp.assign(s + 1, 0);
    for (int i = 1; i <= m; ++i) {
        for (int j = s; j >= a[i].se; --j) {
            dp[j] = max(dp[j], dp[j - a[i].se] + a[i].fi);
        }
    }
    cout << dp[s];
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27