Submission #1163577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163577		YSH2020	Akcija (COCI21_akcija)	C++20	90 / 110	5094 ms	16864 KiB

Main

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

#define int long long

pair<int, long long> solve(vector<pair<int, int>> a, int d) {
	priority_queue<int> taken;
	long long ans = 0;
	for (int i = 0; i < (int)a.size(); i++) {
		if (i == d) continue;
		//case 1:
		if ((int)taken.size() < a[i].first) {
			taken.push(a[i].second);
			ans += a[i].second;
		}
		else {
			//consider to throw away or not
			if (a[i].second < taken.top()) {
				ans -= taken.top();
				taken.pop();
				ans += a[i].second;
				taken.push(a[i].second);
			}
		}
	}
	return {(int) taken.size(), ans} ;
}
bool comp(pair<int, int> x, pair<int, int> y) {
	if (x.first != y.first) return x.first > y.first;
	return x.second < y.second;
};
signed main() {
	int n; cin >> n;
	int count; cin >> count;
	if (count == 0) return 0;
	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; i++) cin >> a[i].second >> a[i].first; //cost, time
	sort(a.begin(), a.end());
	if (n <= 20) {
		vector<pair<int, int>> poss;
		for (int i = 0; i < (1<<n); i++) {
			int total1 = 0, total2 = 0; int possible = 1;
			for (int j = 0; j < n; j++) {
				if ((i&(1<<j)) > 0) {
					total1 += 1;
					total2 += a[j].second;
					if (total1 > a[j].first) {
						possible = 0;
						break;
					}
				}
			}
			if (possible == 1) poss.push_back({total1, total2});
		}
		sort(poss.begin(), poss.end(), comp);
		for (int i = 0; i < count; i++) cout << poss[i].first << ' ' << poss[i].second << '\n';
		return 0;
	}
	else if (count <= 2) {
		pair<int, long long> ans = solve(a, -1);
		cout << ans.first << ' ' << ans.second << '\n';
		if (count > 1) {
			vector<pair<int, int>> tmp(n);
			for (int i = 0; i < n; i++) {
				tmp[i] = solve(a, i);
			}
			sort(tmp.begin(), tmp.end(), comp);
			for (int i = 0; i < n; i++) {
				if (tmp[i] != ans) {
					cout << tmp[i].first << ' ' << tmp[i].second << '\n';
					return 0;
				}
			}
		}
	}
	else{
		vector<int> dp[2][n+1];
		dp[0][0] = {0};
		for (int i = 1; i < n+1; i++) {
			for (int j = 0; j < n+1; j++) {
				if (j > a[i-1].first) continue;
				//case 1: you take
				//case 2: you DONT TAKE. whack it into a PQ.
				priority_queue<int, vector<int>, greater<int>> tmp;
				if (j > 0) {
					for (auto k:dp[0][j-1]) tmp.push(k+a[i-1].second);
				}
				for (auto k:dp[0][j]) tmp.push(k);
				int x = min(count, (int)tmp.size());
				for (int l = 0; l < x; l++) {dp[1][j].push_back(tmp.top()); tmp.pop();}
			}
			for (int j = 0; j < n+1; j++) dp[0][j] = dp[1][j];
			for (int j = 0; j < n+1; j++) dp[1][j] = {};
		}
		int c = 0;
		
		for (int i = n; i >= 0; i--) {
			for (auto j:dp[0][i]) {
				cout << i << ' ' << j << '\n';
				c++;
				if (c == count) return 0;
			}
			
		}
		return 0;
	}

}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 30 / 30
• Subtask 6: 0 / 20