Submission #1247667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247667		ethkc256	Knapsack (NOI18_knapsack)	C++20	100 / 100	45 ms	18500 KiB

knapsack

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

int V[100005] = {}, W[100005] = {}, K[100005] = {};
int DP[2005][2005] = {};
int DP2[2][2005] = {};
priority_queue <pair <int, int>> items[2005];

bool comp(pair <int, int> A, pair <int, int> B) {
    return (A.first > B.first);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int S, N;
	cin >> S >> N;
	for (int i = 1; i <= N; i++) {
		cin >> V[i] >> W[i] >> K[i];
		K[i] = min(K[i], S);
        items[W[i]].push(make_pair(V[i], K[i]));
	}
    for (int i = 1; i <= S; i++) {
        int s = 0, idx = 1;
        while (!items[i].empty() && idx <= S) {
            auto X = items[i].top();
            while (X.second > 0) {
                X.second--;
                s += X.first;
                DP[i][idx] = s;
                idx++;
                if (idx > S)
                    break;
            }
            items[i].pop();
        }
    }
    for (int i = 1; i <= S; i++) {
        for (int target = 0; target <= S; target++) {
            for (int j = 0; j <= S; j++) {
                if (target - i*j < 0)
                    break;
                DP2[1][target] = max(DP2[1][target], DP2[0][target - i*j] + DP[i][j]);
            }
        }
        swap(DP2[0], DP2[1]);
    }
    cout << DP2[0][S];
	return 0;
}

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