제출 #1319363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319363		111	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	436 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int S,N;
	cin>>S>>N;

	long long dp[2001];
	for(int i=0;i<=S;i++)
	{
		dp[i]=0;
	}

	for(int i=1;i<=N;i++)
	{
		long long V,W,K;
		cin>>V>>W>>K;

		long long c=1;
		while(K>0)
		{
			long long t=min(c,K);
			long long wt=t*W;
		 long long val=t*V;

			if(wt<=S)
			{
				for(int s=S;s>=wt;s--)
				{
					dp[s]=max(dp[s],dp[s-wt]+val);
				}
			}

			K-=t;
			c<<=1;
		}
	}

	long long r=0;
	for(int i=0;i<=S;i++)
	{
		r=max(r,dp[i]);
	}

	cout<<r;
	return 0;
}

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