Submission #1163603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163603		gelastropod	Akcija (COCI21_akcija)	C++20	90 / 110	513 ms	589824 KiB

Main

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

signed main() {
	int n, K, a, b;
	cin >> n >> K;
	vector<vector<int>> vals(n + 1, vector<int>());
	vector<pair<int, int>> valss;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		vals[b].push_back(a);
		valss.push_back({b, a});
	}
	sort(valss.begin(), valss.end());
	for (int i = 1; i <= n; i++)
		sort(vals[i].begin(), vals[i].end());
	vector<vector<vector<int>>> dp(n, vector<vector<int>>(n + 1, vector<int>(K, LLONG_MAX)));
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			dp[0][0][0] = 0;
			for (int j = 0; j < min(K, (int)vals[1].size()); j++) {
				dp[0][1][j] = vals[1][j];
			}
			continue;
		}
		vector<pair<int, int>> crntsum = {{0, -1}};
		dp[i][0][0] = 0;
		for (int j = 0; j < (int)vals[i + 1].size(); j++) {
			auto acrntsum = crntsum;
			crntsum.clear();
			for (auto l : acrntsum) {
				for (int k = l.second + 1; k < (int) vals[i + 1].size(); k++) {
					crntsum.push_back({l.first + vals[i + 1][k], k});
				}
			}
			sort(crntsum.begin(), crntsum.end());
			while ((int)crntsum.size() > K)
				crntsum.pop_back();
			for (int k = j + 1; k <= i + 1; k++) {
				vector<int> aaa = dp[i][k];
				for (int l = 0; l < K; l++) {
					if (dp[i - 1][k - j - 1][l] == LLONG_MAX) break;
					for (int m = 0; m < (int)crntsum.size(); m++) {
						aaa.push_back(dp[i - 1][k - j - 1][l] + crntsum[m].first);
					}
				}
				sort(aaa.begin(), aaa.end());
				for (int l = 0; l < K; l++) {
					dp[i][k][l] = aaa[l];
				}
			}
		}
		for (int j = 1; j <= n; j++) {
			vector<int> aaa = dp[i][j];
			for (int k = 0; k < K; k++)
				aaa.push_back(dp[i - 1][j][k]);
			sort(aaa.begin(), aaa.end());
			for (int k = 0; k < K; k++)
				dp[i][j][k] = aaa[k];
		}
	}
	int kkk = K;
	for (int i = n; i >= 0; i--) {
		for (int j = 0; j < K; j++) {
			if (dp.back()[i][j] == LLONG_MAX) break;
			cout << i << ' ' << dp.back()[i][j] << '\n';
			kkk--;
			if (kkk == 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