Submission #624308

#	Time	Username	Problem	Language	Result	Execution time	Memory
624308		pi61	Knapsack (NOI18_knapsack)	C++14	100 / 100	149 ms	17936 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int s,n,ans;
int dp[2005][2005];
struct item
{
	int val,weight,cnt;
};
item a[100005];
vector<int> p[2005];
bool comp(item a, item b)
{
	return (a.weight < b.weight or (a.weight == b.weight and a.val > b.val));
}
int main()
{
	cin>>s>>n;
	for (int i = 1; i <= n; i++)
	{
		cin>>a[i].val>>a[i].weight>>a[i].cnt;
	}
	sort(a+1,a+1+n,comp);
	for (int i = 1; i <= n; i++)
	{
		int w=a[i].weight,k=a[i].cnt;
		while (p[w].size() < (s/w) and k > 0)
		{
			if (!p[w].empty()) p[w].push_back(a[i].val + p[w].back());
			else p[w].push_back(a[i].val);
			k--;
		}
	}

	for (int i = 1; i <= s; i++)
	{
		for (int j = 1; j <= s; j++)
		{
			dp[i][j]=dp[i-1][j];
			for (int cnt = 0; cnt < p[i].size(); cnt++)
			{
				if (j - (cnt + 1)*i < 0) continue;
				dp[i][j]=max(dp[i][j],dp[i-1][j-(cnt+1)*i] + p[i][cnt]);
			}	
			ans=max(ans,dp[i][j]);
		}
	}
//	for (int i = 1; i <= s; i++) cout<<p[i].size()<<' ';cout<<endl;
//	for (int i = 1; i <= s; i++)
//	{
//		for (int j = 1; j <= s; j++)
//		{
//			cout<<dp[i][j]<<' ';
//		}
//		cout<<endl;
//	}
	cout<<ans;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |   while (p[w].size() < (s/w) and k > 0)
      |          ~~~~~~~~~~~~^~~~~~~
knapsack.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for (int cnt = 0; cnt < p[i].size(); cnt++)
      |                      ~~~~^~~~~~~~~~~~~

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