Submission #817794

#	Time	Username	Problem	Language	Result	Execution time	Memory
817794		OAleksa	Knapsack (NOI18_knapsack)	C++14	100 / 100	153 ms	250544 KiB

knapsack

#include <bits/stdc++.h>
//#include "factories.h"
#define f first
#define s second
#define int long long
using namespace std; 
const int maxn = 2010;
vector<pair<int, int>> g[maxn];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		int s, n;
		cin >> s >> n;
		int v[n], w[n], k[n];
		for(int i = 0;i < n;i++) {
			cin >> v[i] >> w[i] >> k[i];
			g[w[i]].push_back({v[i], k[i]});
		}
		vector<int> a, b;
		a.push_back(0);
		b.push_back(0);
		//a-tezina, b-value
		for(int i = 1;i <= s;i++) {
			sort(g[i].begin(), g[i].end());
			reverse(g[i].begin(), g[i].end());
			int x = s / i, ptr = 0;
			while(x > 0 && ptr < (int)g[i].size()) {
				if(x >= g[i][ptr].s) {
					x -= g[i][ptr].s;
					for(int j = 0;j < g[i][ptr].s;j++) {
						a.push_back(i);
						b.push_back(g[i][ptr].f);
					}
				}
				else {
					for(int j = 0;j < x;j++) {
						a.push_back(i);
						b.push_back(g[i][ptr].f);
					}
					x = 0;
				}
				ptr++;
			}
		}
		int m = a.size();
		vector<vector<int>> dp(m, vector<int>(s + 1));
		for(int i = 1;i < m;i++) {
			for(int j = 1;j <= s;j++) {
				if(j < a[i])
					dp[i][j] = dp[i - 1][j];
				else
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + b[i]);
			}
		}
		cout << dp[m - 1][s];
	}
   return 0;
}

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