Submission #688653

#	Time	Username	Problem	Language	Result	Execution time	Memory
688653		tcmmichaelb139	Knapsack (NOI18_knapsack)	C++17	49 / 100	3 ms	1876 KiB

knapsack

#include "bits/stdc++.h"
using namespace std;

struct node {
    long long v, w, k;
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    long long s, n;
    cin >> s >> n;
    vector<node> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].v >> v[i].w >> v[i].k;

    sort(begin(v), end(v), [](node a, node b) {
        if (a.v == b.v) return a.w < b.w;
        return a.v > b.v;
    });

    long long dp[n + 1][s + 1];
    memset(dp, 0, sizeof dp);

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        for (long long j = s; j >= 0; j--) {
            long long num = min(v[i].k, (s - j) / v[i].w);
            dp[i + 1][j + v[i].w * num] = max(dp[i + 1][j + v[i].w * num], dp[i][j] + num * v[i].v);
            ans = max(ans, dp[i + 1][j + v[i].w * num]);

            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            ans = max(ans, dp[i + 1][j]);

            if (j + v[i].w <= s) {
                dp[i + 1][j + v[i].w] = max(dp[i + 1][j + v[i].w], dp[i][j] + v[i].v);
                ans = max(ans, dp[i + 1][j + v[i].w]);
            }
        }
    }

    cout << ans << '\n';
}

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