Submission #1137272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137272		gadun	Knapsack (NOI18_knapsack)	C++20	100 / 100	42 ms	2884 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;
using ll = long long;
const int MOD = 13371337;
const int INF = INT_MAX;
const int MAXN = 1e9;
#define ci pair<char,ll>
#define ii pair<int, int>
#define iii pair<ll, pair<ll, ll>>
#define fi first
#define mp(x,y) make_pair(x, y)
#define se second
#define show(x) cerr << #x << " is " << x << endl;
#define f0r(n) for(int i = 0; i < n; i++)
#define int long long

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int s, n;
	cin >> s >> n;
	vector<vector<ii>> v(s+1);
	vector<int> a(s+1, 0);
	for (int i =1 ; i <= n; i++){
		int val, weight, amt;
		cin >> val >> weight >> amt;
		v[weight].push_back(make_pair(val, amt));
		a[weight] += amt;
	}
	for (int i = 1; i <= s; i++){
		sort(v[i].begin(), v[i].end(), greater<ii>());
	}
	int dp[s+1];
	memset(dp, 0, sizeof dp);


	int it = 0;
	for (int i = 1; i <= s; i++){
		if (v[i].empty()) continue;
		int id = 0, cap = v[i][id].se, amt = min(a[i], s/i);
		while(amt){
			for (int j = s; j >= 1; j--){
				
				if (j >= i) dp[j] = max(dp[j], dp[j-i] + v[i][id].fi);
			}
			amt--;
			cap--;
			it++;
			if (cap == 0 && amt){
				id++;
				cap = v[i][id].se;
			}
		}
	}
	
	
	int ans = -1e9;
	for (int j = 0; j <= s;j ++){
		ans = max(ans, dp[j]);
	}
	show(it);
	cout << ans << endl;
}

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