Submission #1271341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271341		tinyfold	Knapsack (NOI18_knapsack)	C++20	100 / 100	88 ms	2888 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2100;
vector<pair<int, int>> vecs[N];
int dp[N];
int k, n, x, y, z;

void solve(int x, int y) {
    for (int i = k; i >= x; i--) {
        dp[i] = max(dp[i], dp[i - x] + y);
    }
}

signed main() {
    cin >> k >> n;
    while (n--) {
        cin >> x >> y >> z;
        vecs[y].push_back({x, z});
    }
    for (int i = 1; i <= k; i++) {
        sort(vecs[i].begin(), vecs[i].end());
        for (int j = 1; j <= k / i && vecs[i].size(); j++) {
            solve(i, vecs[i].back().first);
            if (!--vecs[i].back().second) vecs[i].pop_back();
        }
    }
    cout << dp[k] << endl;
    return 0;
}

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