Submission #650280

#	Time	Username	Problem	Language	Result	Execution time	Memory
650280		ono_de206	Knapsack (NOI18_knapsack)	C++14	73 / 100	1085 ms	3948 KiB

knapsack

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

#define int long long

const int mxn=1e5+10;
const int mxm=2010;

int dp[mxm];
int dp1[mxm];
signed main(){
//	freopen("feast.in","r",stdin);
//	freopen("feast.out","w",stdout);
	int s,n;
	cin>>s>>n;
	vector<int> v(n),w(n),k(n);
	for(int i=0; i<n; i++) cin>>v[i]>>w[i]>>k[i];
	for(int i=0; i<n; i++){
		for(int j=1; j<=min(k[i],s/w[i]); j++){
			for(int k=s; k>=w[i]; k--) dp[k]=max(dp[k],dp[k-w[i]]+v[i]);
		}
	}
	int ans=0;
	for(int i=1; i<=s; i++) ans=max(ans,dp[i]);
	cout<<ans<<'\n';
	return 0;
}

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