Submission #726628

#	Time	Username	Problem	Language	Result	Execution time	Memory
726628		Azther0z	Knapsack (NOI18_knapsack)	C++11	100 / 100	149 ms	35188 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
struct ITEM
{
	int value,copy;
	bool operator<(const ITEM item)
	{
		if(value!=item.value) return value>item.value;
		return copy>item.copy;
	}
};
int main()
{
	int s,n;
	cin >> s >> n;
	map<int,vector<ITEM>> weight;
	for(int i=0;i<n;i++)
	{
		int v,w,k;
		cin >> v >> w >> k;
		weight[w].push_back({v,k});
	}
	long long result=0;
	vector<vector<long long>> dp(weight.size()+1,vector<long long>(s+1,-1));
	dp[0][0]=0;
	int at=1;
	for(auto &ww:weight)
	{
		int w=ww.first;
		vector<ITEM> item=ww.second;
		sort(item.begin(),item.end());
		for(int i=0;i<=s;i++)
		{
			dp[at][i]=dp[at-1][i];
			int copy=0,idx=0,use=0;
			long long value=0;
			while((copy+1)*w<=i&&idx<item.size())
			{
				copy++;
				value+=item[idx].value;
				if(dp[at-1][i-copy*w]!=-1)
					dp[at][i]=max(dp[at][i],dp[at-1][i-copy*w]+value);
				result=max(result,dp[at][i]);
				use++;
				if(use==item[idx].copy)
				{
					use=0;
					idx++;
				}
			}
		}
		at++;
	}
	cout << result;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:37:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ITEM>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    while((copy+1)*w<=i&&idx<item.size())
      |                         ~~~^~~~~~~~~~~~

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