Submission #1163518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163518		YSH2020	Akcija (COCI21_akcija)	C++20	60 / 110	170 ms	16796 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 k; cin >> k;
	if (k == 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 < k; i++) cout << poss[i].first << ' ' << poss[i].second << '\n';
		return 0;
	}
	pair<int, long long> ans = solve(a, -1);
	cout << ans.first << ' ' << ans.second << '\n';
	if (k > 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;
			}
		}
	}
}

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