Submission #1037019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037019		inkvizytor	Knapsack (NOI18_knapsack)	C++17	100 / 100	43 ms	3932 KiB

knapsack

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int s, n;
    cin >> s >> n;
    vector<pair<pair<int, int>, int>> p (n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].first.second >> p[i].first.first >> p[i].second;
    }
    sort(p.begin(), p.end(), greater<pair<pair<int, int>, int>>());
    vector<vector<int>> u (s+1);
    vector<int> pos (s+1, 0);
    for (int i = 1; i < s+1; i++) {
        u[i].resize(s/i, -1);
    }
    for (auto x : p) {
        for (int i = 0; i < x.second; i++) {
            if (pos[x.first.first] >= s/x.first.first) {
                break;
            }
            u[x.first.first][pos[x.first.first]] = x.first.second;
            pos[x.first.first]++;
        }
    }
    vector<int> dp (s+1, -1);
    dp[0] = 0;
    for (int i = 1; i <= s; i++) {
        for (auto x : u[i]) {
            if (x == -1) {
                break;
            }
            for (int j = s-i; j >= 0; j--) {
                dp[j+i] = max(dp[j+i], dp[j]+x);
            }
        }
    }
    int maks = 0;
    for (int i : dp) {
        maks = max(i, maks);
    }
    cout << maks << '\n';
}

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