Submission #998073

#	Time	Username	Problem	Language	Result	Execution time	Memory
998073		coolboy19521	Knapsack (NOI18_knapsack)	C++17	73 / 100	431 ms	262144 KiB

knapsack

#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"

#define int long long

using namespace std;

const int sz = 1e5 + 5;
const int sm = 2e3 + 3;

int dp[sm][sz];
bool v[sz];

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

    int n, s;

    cin >> s >> n;

    vector <int> a, b;
    a = {0}, b = {0};

    for (int i = 1; i <= n; i ++) {
        int v, w, k;
        cin >> v >> w >> k;

        for (int j = 0; (1 << j) < k; j ++) {
            a.push_back((1 << j) * v);
            b.push_back((1 << j) * w);
            k -= (1 << j);
        }

        if (0 < k) {
            a.push_back(k * v);
            b.push_back(k * w);
        }
    }

    int m = a.size() - 1;
/*
    for (int i = 1; i <= m; i ++) {
        cout << a[i] << ' ' << b[i] << '\n';
    }
*/
    v[0] = true;

    for (int i = 1; i <= m; i ++) {
        for (int j = s; 0 <= j - b[i]; j --) {
            if (v[j - b[i]]) {
                dp[j][i] = dp[j - b[i]][i - 1] + a[i];
                v[j] = true;
            }
        }

        for (int j = s; 0 <= j; j --) {
            dp[j][i] = max(dp[j][i], dp[j][i - 1]);
        }
    }

    int mx = 0;

    for (int i = 0; i <= s; i ++) {
        mx = max(mx, dp[i][m]);
    }

    cout << mx << '\n';
}

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