Submission #502014

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

int dp[1050][40000];

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 = 2000 / currweight;
	for (int i = 0; i < N; i++) {
		if (types[i].weight != currweight || currneeded == 0) {
			currweight = types[i].weight;
			currneeded = 2000 / currweight;
		}
		int 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;
	}
*/
	int maximum = 0;
	for (int i = 1; i < 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;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 1; i < items.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

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