Submission #810909

#	Time	Username	Problem	Language	Result	Execution time	Memory
810909		Acanikolic	Knapsack (NOI18_knapsack)	C++14	49 / 100	1087 ms	360 KiB

knapsack

#include <bits/stdc++.h>
			 		
#define int long long 
			 
#define pb push_back 
			
#define F first
			 
#define S second
			 
using namespace std;
			 
const int N = 2e5+10;
			 
const int mod = 1e9+7;
			 
const int inf = 1e18;

int v[N],w[N],k[N];
		
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
	 
    int s,n;
    cin >> s >> n;
    for(int i=1;i<=n;i++) {
    	cin >> v[i] >> w[i] >> k[i];
    }
    vector<int>dp(s+1);
    for(int i=1;i<=n;i++) {
    	vector<int>new_dp = dp;
    	for(int j=1;j<=k[i];j++) {
    		for(int o=w[i]*j;o<=s;o++) new_dp[o] = max(new_dp[o],dp[o-w[i]*j]+v[i]*j);
    	//	for(int o=1;o<=s;o++) cout << dp[o] << ' ';
    	//	cout << endl;
    	}
    	swap(dp,new_dp);
    }
    cout << dp[s];
}

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