제출 #1151935

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

knapsack

#include<bits/stdc++.h>
#define int long long
#define ss second
#define ff first
#define pb push_back
const int mxn=1e6+5;
const int mod=998244353;
using namespace std;
int s,n,c;
int v[mxn+30],w[mxn+30];
int dp[2005];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>s>>n;
	for(int i=1; i<=n; i++) {
		int wi,vi,ki;
	 	cin>>vi>>wi>>ki;
	 	int t=1;
	 	while(ki>=t) {
	 		c++;
	 		v[c]=vi*t;
	 		w[c]=wi*t;
	 		ki-=t;
	 		t*=2;
		 }
		 if(ki>0) {
		 	c++;
		 	v[c]=vi*ki;
		 	w[c]=wi*ki;
		 }
	 }
	 for(int i=1; i<=c; i++) {
	 	for(int j=s; j>=w[i]; j--) {
	 		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		 }
	 }
	 cout<<dp[s];
}

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