Submission #1320047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320047		i_love_spring	Knapsack (NOI18_knapsack)	C++20	100 / 100	69 ms	33116 KiB

knapsack

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

#define ll long long 
#define ar array

void solve() {
    int m, n;
    cin >> m >> n;
    
    vector<vector<ll>> dp(m + 1, vector<ll> (m + 1, 0));

    vector<ar<int, 2>> W[m + 1];
    for (int i = 0; i < n;i++) {
        int x, y, z; cin >> x >> y >> z;
        if (y <= m) W[y].push_back({x, z});
    }


    for (int i = 1; i <= m;i++) {
        sort(W[i].rbegin(), W[i].rend());
        for (int j = 1; j <= m;j++) {
            dp[i][j] = dp[i - 1][j];
            ll val = 0;
            int id = 0;
            int taken = 0;
            for (int k = 1; k * i <= j;k++) {
                if (id < W[i].size() && W[i][id][1] == taken) {
                    id++;
                    k--;
                    taken = 0;
                    continue;
                }
                if (id < W[i].size()) {
                    taken++;
                    val += W[i][id][0];
                }
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * i] + val);
            }
        }
    }

    cout << *max_element(dp.back().begin(), dp.back().end());

}


signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}

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