Submission #749207

#	Time	Username	Problem	Language	Result	Execution time	Memory
749207		hippo123	Knapsack (NOI18_knapsack)	C++17	12 / 100	4 ms	3412 KiB

knapsack

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

#define ll long long
#define pr pair<ll, ll>
#define f first
#define s second

int main(){

	

	int s, n; cin>>s>>n;
	
	vector<int> v(n+1);
	vector<int> w(n+1);
	vector<int> k(n+1);
	
	for  (int i=1; i<=n; i++){
		cin>>v[i]>>w[i]>>k[i];
	}
	
	vector<vector<pr>> dp(n+1, vector<pr>(s+1, {0, 0}));
	
	for (int i=1; i<=n; i++){
		for (int j=0; j<=s; j++){
			if(j+w[i]<=s){
				// from the same row
				if((dp[i][j].f>0 || j==0) && dp[i][j].s<k[i]) {	
					dp[i][j+w[i]].f=max(dp[i][j+w[i]].f, dp[i][j].f+v[i]);
					dp[i][j+w[i]].s=dp[i][j].s+1; 				
				}
				// from previous row
				if(dp[i-1][j].f>0){
					dp[i][j+w[i]].f=max(dp[i][j+w[i]].f, dp[i-1][j].f+v[i]); 
					dp[i][j+w[i]].s=1;
				}
			}
		}			
	}
	/*
	for (int j=1; j<=s; j++) cout<<j<<" ";
	cout<<endl;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=s;j++){
			cout<<dp[i][j].f<<" ";
		}
		cout<<endl;
	}
	for (int j=1; j<=s;j++) cout<<j<<" ";
	cout<<endl;
	
	for (int i=1; i<=n; i++){
		
		for (int j=1; j<=s;j++){
			cout<<dp[i][j].s<<" ";
		}
		cout<<endl;
	}	
	*/
	ll results=0;
	
	for (int i=1; i<=n; i++){
		for (int j=s; j>=0;j--){
			if(dp[i][j].f>0) {
				results=max(results, dp[i][j].f);
				break;
			}
		}
	}
	cout<<results;


}

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