Submission #1133772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133772		NAMIN	Knapsack (NOI18_knapsack)	C++20	73 / 100	146 ms	327680 KiB

knapsack

/*
ID: NAMIN
TASK:
LANG: C++
*/
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <numeric>
#include <math.h>
#include <set>
#include <unordered_set>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>
#include <fstream>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <assert.h>

#define gcd __gcd
#define endl "\n"
#define ll long long
#define ld long double
#define f first
#define s second

using namespace std;

const int MOD = 1e9+7;

void solve(){
	//ifstream cin("snakes.in");
	//ofstream cout("snakes.out");
	
	int S,N;
	cin >> S >> N;
	ll dp[N+1][S+1];
	memset(dp,-1e9,sizeof(dp));
	for(int i=0;i<=N;i++)
		dp[i][0] = 0;

	for(int i=1;i<=N;i++){
		ll v,x,k;
		cin >> v >> x >> k;
		for(int w=S;w>=0;w--){
			dp[i][w] = max(dp[i][w],dp[i-1][w]);
			if(w-x >= 0 && dp[i-1][w-x] != -1e9){
				dp[i][w] = max(dp[i][w],dp[i-1][w-x]+v);
			}
		}
		k--;
		bool ismore = true;
		while(ismore && k--){
			ismore = false;
			for(int w=S;w>=0;w--){
				//dp[i][w] = max(dp[i][w],dp[i-1][w]);
				if(w-x >= 0 && dp[i][w-x] != -1e9){
					if(dp[i][w] < dp[i][w-x]+v){
						ismore = true;
						dp[i][w] = max(dp[i][w],dp[i][w-x]+v);
					}
				}
			}
		}
	}
	ll ans = 0;
	for(int i=0;i<=S;i++){
		ans = max(ans,dp[N][i]);
	}
	cout << ans << endl;
}

int main(){
// CHILL & \/\/\/\/\/\/\/
//[======================]
//|FOLLOW THE **METHODE**|
//[======================]

	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

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