Submission #1153364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153364		Tsagana	Knapsack (NOI18_knapsack)	C++20	100 / 100	50 ms	5192 KiB

knapsack

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int s, n, dp[2010];
vector<pair<int, int>> v[100010];

void solve () {
	cin >> s >> n;
	for (int i = 0; i < n; i++) {
		int x, y, k;
		cin >> x >> y >> k;
		v[y].pb({x, k});
	}
	for (int i = 1; i <= s; i++) {
		sort(all(v[i]), greater<pair<int, int>>());
		int y = 0;
		for (auto [x, k]: v[i]) {
			while (y + i <= s && k) {
				k--;
				y += i;
				for (int j = s; j >= i; j--) dp[j] = max(dp[j], dp[j - i] + x);
			}
			if (y + i > s) break;
		}
	}
	cout << dp[s];
}
signed main() {IOS solve(); return 0;}

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