Submission #952264

#	Time	Username	Problem	Language	Result	Execution time	Memory
952264		BF001	Knapsack (NOI18_knapsack)	C++17	100 / 100	44 ms	3920 KiB

knapsack

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

#define M 2005
#define fi first
#define se second
#define log 11

typedef pair<int, int> ii;

int dp[M], n, s, pw[log + 5];
vector<ii> sov[M];
vector<ii> g;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    pw[0] = 1;
    for (int i = 1; i <= log; i++) pw[i] = pw[i - 1] * 2;

    cin >> s >> n;
	for (int i = 1; i <= n; i++){
		int w, v, k;
		cin >> v >> w >> k;
		sov[w].push_back({v, k});
	}

	for (int i = 1; i <= s; i++){
		sort(sov[i].begin(), sov[i].end(), greater<ii>());
		int gt = s;
		for (auto x : sov[i]){
			int v = x.fi, k = x.se;
			k = min(k, gt / i);
			int d = -1;
			while (pw[d + 1] * i <= gt && pw[d + 1] <= k && gt > 0){
				k -= pw[d + 1];
				gt -= pw[d + 1] * i;
				d++;
				g.push_back({pw[d] * i, pw[d] * v});
			}
			if (k > 0) {
				k = min(k, gt / i);
				gt -= k * i;
				if (k > 0)
				g.push_back({k * i, k * v});
			}
		}
	}

	int res = 0;

	for (auto x : g){
		int w = x.fi;
		int v = x.se;
		for (int j = s; j >= 0; j--){
			if (j >= w) dp[j] = max(dp[j], dp[j - w] + v);
			res = max(res, dp[j]);
		}
	}

	cout << res;	

    return 0;
}     

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