Submission #1264973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264973		marshziin	Knapsack (NOI18_knapsack)	C++20	12 / 100	32 ms	75592 KiB

knapsack

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

#define int long long
#define pii pair<int,int>

const int inf = 1e9 + 10;
const int maxw = 3100;
int dp[maxw][maxw];

void init() {
    for (int i = 0; i < maxw; i++)
        for (int j = 0; j < maxw; j++)
            dp[i][j] = -inf;
    dp[0][0] = 0;
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    init();

    int s, n; cin >> s >> n;
    map<int, vector<pii>> W;

    for (int i = 0; i < n; i++) {
        int v, w, k; cin >> v >> w >> k;
        W[w].push_back({v, k});
    }

    int cur = 1;
    for (auto [weight, items] : W) {
        sort(items.begin(), items.end(), greater<pii>());

        for (int i = 1; i <= s; i++) {
            dp[cur][i] = dp[cur - 1][i];

            int cnt = 0;
            int sum = weight, pos = 0, cum = 0;
            while(sum <= s && pos < items.size()) {
                if (cnt == items[pos].second) {
                    pos++;
                    cnt = 0;
                    continue;
                }
                cum += items[pos].first;
                if(i >= sum) dp[cur][i] = max(dp[cur][i], dp[cur - 1][i - sum] + cum); 

                sum += weight; cnt++;
            }

        }
        cur++;
    }

    int res = 0;
    for (int i = 1; i <= s; i++)    
        res = max(res, dp[cur - 1][i]);
    cout << res << '\n';
    return 0;
}

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