Submission #502100

#	Time	Username	Problem	Language	Result	Execution time	Memory
502100		pawned	Knapsack (NOI18_knapsack)	C++17	100 / 100	146 ms	2332 KiB

knapsack

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

struct itemtype {
	int weight, cost, number;
};

bool cmp(const itemtype& x, const itemtype& y) {
	if (x.weight != y.weight)
		return x.weight < y.weight;
	if (x.cost != y.cost)
		return x.cost > y.cost;
	if (x.number != y.number)
		return x.number < y.number;
	return true;
}

int main() {
	int S, N;	// maxweight, itemcount
	cin>>S>>N;
	itemtype types[N];	// weight, cost, number
	for (int i = 0; i < N; i++) {
		cin>>types[i].cost>>types[i].weight>>types[i].number;
	}
	sort(types, types + N, cmp);
	vector<ii> items;	// {weight, cost}
	items.pb({-1, -1});
	int currweight = -1;
	int currneeded = -1;
	for (int i = 0; i < N; i++) {
		if (currneeded <= 0 && types[i].weight == currweight)
			continue;
		if (types[i].weight != currweight) {
			currweight = types[i].weight;
			currneeded = S;
		}
		while (types[i].number > 0 && currneeded >= currweight) {
			items.pb({types[i].weight, types[i].cost});
			types[i].number--;
			currneeded -= currweight;
		}
	}
/*
	for (int i = 0; i < items.size(); i++) {
		cout<<"item "<<i<<": "<<items[i].first<<", "<<items[i].second<<endl;
	}
*/
	int dpbefore[S + 5];
	for (int i = 0; i < S + 5; i++) {
		dpbefore[i] = 0;
	}
	int dpafter[S + 5];
	for (int i = 0; i < S + 5; i++) {
		dpafter[i] = 0;
	}
	int maximum = 0;
	for (int i = 1; i < (int)(items.size()); i++) {
		copy(dpafter, dpafter + (S + 5), dpbefore);
		for (int j = 1; j <= S; j++) {
			dpafter[j] = dpbefore[j];
			if (j >= items[i].first)
				dpafter[j] = max(dpafter[j], dpbefore[j - items[i].first] + items[i].second);
//			cout<<i<<" "<<j<<": "<<dp[i][j]<<endl;
			maximum = max(maximum, dpafter[j]);
		}
	}
	cout<<maximum<<endl;
}

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