Submission #869902

#	Time	Username	Problem	Language	Result	Execution time	Memory
869902		cuman	Knapsack (NOI18_knapsack)	C++14	100 / 100	110 ms	3408 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define between(l,x,r) ((l) <= (x) && (x) <= (r))
#define len(v) (i64((v).size()))
using i64 = long long;

const i64 MaxN = 1e5;
const i64 MaxS = 2e3;

i64 S, N;
array<i64,3> VWK[MaxN];

vector<i64> VByWeight[MaxS+1];

// (V, W)
vector<pair<i64,i64>> flatten;

i64 DPi[MaxS + 1], DPiplusone[MaxS + 1];

signed main() {
	fill(VByWeight, VByWeight + MaxS + 1, vector<i64>(0));

	cin >> S >> N;
	for (i64 i = 0; i < N; i++) cin >> VWK[i][0] >> VWK[i][1] >> VWK[i][2];

	sort(VWK, VWK + N, greater<array<i64,3>>());

	for (i64 i = 0; i < N; i++) {
		i64 v = VWK[i][0], w = VWK[i][1], k = VWK[i][2];
		i64 timesToAdd = min(k, S/w - len(VByWeight[w]));
		for (i64 j = 0; j < timesToAdd; j++) {
			VByWeight[w].push_back(v);
		}
	}

	for (i64 w = 0; w <= S; w++) {
		for (i64 v : VByWeight[w]) {
			flatten.push_back({v, w});
		}
	}

	for (i64 i = len(flatten) - 1; i >= 0; i--) {
		for (i64 curS = 0; curS <= S; curS++) {
			i64 r1 = DPiplusone[curS];
			i64 r2 = curS >= flatten[i].second ? DPiplusone[curS - flatten[i].second] + flatten[i].first : 0;
			DPi[curS] = max(r1, r2);
		}

		copy(DPi, DPi + S + 1, DPiplusone);
		fill(DPi, DPi + S + 1, 0);
	}

	i64 res = DPiplusone[S];
	cout << res;
	return 0;
}

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