Submission #652637

#	Time	Username	Problem	Language	Result	Execution time	Memory
652637		clams	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	596 KiB

knapsack

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

const int N = 2e5 + 5;
const int W = 3005;

struct Item {
	ll exp;
	ll k;
	
	// reverse because it is used in priority_queue
	bool operator < (const Item& oth) const {
		if (exp == oth.exp) {
			return k > oth.k;
		}
		return exp < oth.exp;
	}
};

int n;
ll w;
ll ans = 0;
priority_queue<Item> a[W];
vector<pair<int, int>> all;
ll dp[2][W];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> w >> n;
	for (int i = 1; i <= n; i++) {
		ll energy;
		Item x;
		cin >> energy >> x.exp >> x.k;
		
		a[energy].push(x);
	}
	
	// energy == 0?
	assert(a[0].empty());
	
	for (int i = 1; i <= w; i++) {
		int cur = w;
		priority_queue<Item>& pq = a[i];
		while (pq.size() && cur > 0) {
			Item u = pq.top();
			pq.pop();
			
			if (u.exp < 0 || cur < i) {
				continue;
			}
			
			all.push_back(make_pair(i, u.exp));
			
			u.exp -= u.k;
			cur -= i;
			pq.push(u);
		}
	}
	
	ll ans = 0;
	int now = 0, pre = 1;
	int sz = all.size();
	for (int i = 1; i <= sz; i++) {
		swap(now, pre);
		for (int j = 0; j <= w; j++) {
			dp[now][j] = dp[pre][j];
			int nj = j - all[i - 1].first;
			if (nj >= 0) {
				dp[now][j] = max(dp[now][j], dp[pre][nj] + all[i - 1].second);
			}
		}
	}
	
	cout << dp[now][w] << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:63:5: warning: unused variable 'ans' [-Wunused-variable]
   63 |  ll ans = 0;
      |     ^~~

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