Submission #624305

#	Time	Username	Problem	Language	Result	Execution time	Memory
624305		pi61	Knapsack (NOI18_knapsack)	C++14	29 / 100	47 ms	63124 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int s,n,ans;
pair<int,int> dp[2005][2005][2];
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 and k > 0)
		{
			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][0].first=dp[i][j][1].first=-1;

	for (int i = 1; i <= s; i++)
	{
		for (int j = 0; j <= s; j++)
		{
			for (int bl = 0; bl < 2; bl++)
			{
				if (dp[i][j][bl].first == -1) continue;
				ans=max(ans,dp[i][j][bl].first);
				int cnt = dp[i][j][bl].second;
				if (dp[i+1][j][0].first < dp[i][j][bl].first) dp[i+1][j][0].first=dp[i][j][bl].first;
				if (cnt >= p[i].size() or j + i > s) continue;
				int nextitem = p[i][cnt];
				if (dp[i][j][bl].first + nextitem > dp[i][j + i][1].first) dp[i][j+i][1].first=dp[i][j][bl].first + nextitem, dp[i][j+i][1].second=dp[i][j][bl].second + 1;
			}
		}
	}
//	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].first<<','<<dp[i][j].second<<'}';
		}
		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 and k > 0)
      |          ~~~~~~~~~~~~^~~
knapsack.cpp:44:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     if (cnt >= p[i].size() or j + i > s) continue;
      |         ~~~~^~~~~~~~~~~~~~

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