Submission #1285890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285890		zxzuam	Knapsack (NOI18_knapsack)	C++20	100 / 100	37 ms	1768 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 2E3 + 1;
vector <vector <pair <int, int>>> g(maxn + 1);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int s, n;
    cin >> s >> n;
    for(int i = 1; i <= n; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        k = min(k, s);
        g[ w ].push_back( {v, k} );
    }
    vector <int64_t> dp(s + 61, LLONG_MIN);
    dp[0] = 0LL;
    for(int w = 1; w <= s; w++) {
        int cnt = s / w, cur = 0;
        sort(g[w].begin(), g[w].end());
        reverse(g[w].begin(), g[w].end());
        while(cnt-- && cur < g[w].size()) {
            for(int j = s; j >= w; j--) {
                dp[j] = max(dp[j], dp[j - w] + (int64_t)g[w][cur].first);
            }
            g[w][cur].second--;
            if(g[w][cur].second == 0) cur++;
        }
    }
    cout << *max_element(dp.begin(), dp.end());
}

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