Submission #1163547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163547		siewjh	Akcija (COCI21_akcija)	C++20	90 / 110	5094 ms	32856 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k; cin >> n >> k;
	vector<pair<int, ll>> vec(n);
	for (int i = 0; i < n; i++){
		ll c; int t; cin >> c >> t;
		vec[i] = {t, c};
	}
	sort(vec.begin(), vec.end());
	vector<multiset<ll>> vals(n + 1);
	vals[0].insert(0);
	for (auto [t, c] : vec){
		for (int i = t - 1; i >= 0; i--){
			for (auto it = vals[i].begin(); it != vals[i].end(); it++){
				if (vals[i + 1].size() == k && *(vals[i + 1].rbegin()) <= *it + c) break;
				vals[i + 1].insert(*it + c);
				if (vals[i + 1].size() > k) vals[i + 1].erase(prev(vals[i + 1].end()));
			}
		}
	}
	int cnt = 0;
	for (int i = n; i >= 0; i--)
		for (ll x : vals[i]){
			cout << i << ' ' << x << '\n';
			if (++cnt == k) 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