Submission #1213292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213292		shrek_lover	Knapsack (NOI18_knapsack)	C++20	37 / 100	1095 ms	328 KiB

knapsack

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

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 2020;
long long dp[mxn];
int S, N, LIM[mxn];

int main() {
	cin >> S >> N;
	vector<pair<int, pii>> vec;
	for(int i = 0; i < N; i++) {
		int p, w, k;
		cin >> p >> w >> k;
		vec.push_back({w, {p, k}});
	}

	sort(vec.begin(), vec.end(), [&](auto x, auto y) {
		if(x.ff != y.ff) return x.ff < y.ff;
		return x.ss.ff > y.ss.ff;
	});

	for(int i = 1; i <= S; i++)
		LIM[i] = S / i;

	for(auto item : vec) {
		int w = item.ff;
		int p = item.ss.ff;
		int k = item.ss.ss;
		if(LIM[w] <= 0) continue;

		for(int _ = 0; _ < k; _++) {
			LIM[w]--;
			for(int i = S; i >= w; i--) {
				dp[i] = max(dp[i], dp[i - w] + p);
			}
		}
	}

	cout << dp[S] << endl;
	return 0;
}

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