Submission #502031

#	Time	Username	Problem	Language	Result	Execution time	Memory
502031		pawned	Knapsack (NOI18_knapsack)	C++17	49 / 100	83 ms	78548 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;

ll dp[2050][40000];

struct itemtype {
	ll 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() {
	ll 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<pair<ll, ll>> items;	// {weight, cost}
	items.pb({-1, -1});
	ll currweight = 1;
	ll currneeded = S / currweight;
	for (int i = 0; i < N; i++) {
		if (types[i].weight != currweight || currneeded == 0) {
			currweight = types[i].weight;
			currneeded = S / currweight;
		}
		ll toadd = min(types[i].number, currneeded);
		for (int j = 0; j < toadd; j++) {
			items.pb({types[i].weight, types[i].cost});
		}
		currneeded -= toadd;
	}
/*
	for (int i = 0; i < items.size(); i++) {
		cout<<"item "<<i<<": "<<items[i].first<<", "<<items[i].second<<endl;
	}
*/
	ll maximum = 0;
	for (int i = 1; i < (int)(items.size()); i++) {
		for (int j = 0; j <= S; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j >= items[i].first)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - items[i].first] + items[i].second);
//			cout<<i<<" "<<j<<": "<<dp[i][j]<<endl;
			maximum = max(maximum, dp[i][j]);
		}
	}
	cout<<maximum<<endl;
}

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