Submission #1042940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042940		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	1057 ms	3932 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define pb push_back
#define fi first
#define se second
#define debug(x) cerr << #x << " => " << x << endl
#define all(x) x.begin(),x.end()

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int s,n;cin>>s>>n;
	ll v[n+1],w[n+1],k[n+1];
	for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>k[i];

	ll dp[2][s+1];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=s;j++)
		{
			int m=1;
			dp[i%2][j]=max(dp[i%2][j],dp[(i+1)%2][j]);
			while(m<=k[i] && j+w[i]*m<=s)
			{
				dp[i%2][j+w[i]*m]=max(dp[i%2][j+w[i]*m],dp[(i+1)%2][j]+v[i]*m);
				m++;
			}
		}
		// for(int j=0;j<=s;j++) cout<<dp[i][j]<<' ';cout<<'\n';
	}
	cout<<dp[n%2][s];
	return 0;
}

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