Submission #1163361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163361		boclobanchat	Knapsack (NOI18_knapsack)	C++20	100 / 100	39 ms	1740 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
struct item { int v,w,k; };
bool sortt(item a,item b) { if(a.w==b.w) return a.v>b.v;return a.w<b.w; }
const int MAXN=2024;
const long long INF=1e18;
vector<int> vi[MAXN];
long long dp[MAXN];
item A[MAXN*50];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int s,n;
	cin>>s>>n;
	for(int i=1;i<=n;i++) cin>>A[i].v>>A[i].w>>A[i].k;
	sort(A+1,A+n+1,sortt);
	for(int i=1;i<=n;i++)
	{
		if(A[i].w>s) break;
		while(A[i].k--&&(int)vi[A[i].w].size()*A[i].w<=s) vi[A[i].w].push_back(A[i].v);
	}
	for(int i=1;i<=s;i++) dp[i]=-INF;
	for(int i=1;i<=s;i++)
	{
		for(int j=s;j>=0;j--)
		{
			int p=j;
			long long w=0;
			for(auto v:vi[i])
			{
				if((p+=i)>s) break;
				w+=v,dp[p]=max(dp[p],dp[j]+w);
			}
		}
	}
	long long ans=0;
	for(int i=0;i<=s;i++) ans=max(ans,dp[i]);
	cout<<ans;
}

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