Submission #1183245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183245		Trn115	Knapsack (NOI18_knapsack)	C++17	100 / 100	89 ms	8684 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;
vector<vector<int>> val;
vector<int> dp;

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

    cin >> s >> n;
    val.resize(s + 1);
    while (n--) {
        int v, w, k;
        cin >> v >> w >> k;
        int x = 1;
        while (x <= k) {
            if (w * x <= s) val[w * x].push_back(v * x);
            k -= x;
            x <<= 1;
        }
        if (k && w * k <= s) val[w * k].push_back(v * k);
    }

    for (int i = 1; i <= s; ++i) {
        sort(all(val[i]), greater<int>());
        int len = val[i].size();
        val[i].insert(val[i].begin(), 0);
        for (int j = 1; j <= len; ++j) {
            val[i][j] += val[i][j - 1];
        }
    }

    dp.assign(s + 1, 0);
    for (int i = 1; i <= s; ++i) {
        for (int j = s; j >= i; --j) {
            for (int k = 1; k < val[i].size(); ++k) {
                if (j >= i * k) {
                    dp[j] = max(dp[j], dp[j - i * k] + val[i][k]);
                } else {
                    break;
                }
            }
        }
    }
    cout << dp[s];
}

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