제출 #1163543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163543		gelastropod	Akcija (COCI21_akcija)	C++20	60 / 110	5086 ms	525828 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<pair<int, int>>> dp(n, vector<pair<int, int>>(n + 1, {LLONG_MAX, LLONG_MAX}));
	if (k <= 2) {
		for (int i = 0; i < n; i++) {
			if (i == 0) {
				dp[0][0] = {0, LLONG_MAX};
				if (vals[1].size() == 1)
					dp[0][1] = {vals[1][0], LLONG_MAX};
				else if (vals[1].size() >= 2)
					dp[0][1] = {vals[1][0], vals[1][1]};
				continue;
			}
			int crntsum = 0;
			dp[i][0] = {0, LLONG_MAX};
			for (int j = 0; j < (int)vals[i + 1].size(); j++) {
				crntsum += vals[i + 1][j];
				for (int k = j + 1; k <= i + 1; k++) {
					if (dp[i - 1][k - j - 1].first == LLONG_MAX) continue;
					vector<int> aaa;
					aaa.push_back(dp[i][k].first);
					aaa.push_back(dp[i][k].second);
					aaa.push_back(dp[i - 1][k - j - 1].first + crntsum);
					if ((int)vals[i + 1].size() - 1 != j) {
						aaa.push_back(dp[i - 1][k - j - 1].first + crntsum - vals[i + 1][j] + vals[i + 1][j + 1]);
					}
					if (dp[i - 1][k - j - 1].second != LLONG_MAX) {
						aaa.push_back(dp[i - 1][k - j - 1].second + crntsum);
					}
					sort(aaa.begin(), aaa.end());
					dp[i][k] = {aaa[0], aaa[1]};
				}
			}
			for (int j = 1; j <= n; j++) {
				vector<int> aaa;
				aaa.push_back(dp[i][j].first);
				aaa.push_back(dp[i][j].second);
				aaa.push_back(dp[i - 1][j].first);
				aaa.push_back(dp[i - 1][j].second);
				sort(aaa.begin(), aaa.end());
				dp[i][j] = {aaa[0], aaa[1]};
			}
		}
		for (int i = n; i >= 0; i--) {
			if (dp.back()[i].first != LLONG_MAX) {
				cout << i << ' ' << dp.back()[i].first << '\n';
				k--;
				if (k == 0)
					return 0;
			}
			if (dp.back()[i].second != LLONG_MAX) {
				cout << i << ' ' << dp.back()[i].second << '\n';
				k--;
				if (k == 0)
					return 0;
			}
		}
	}
	else {
		vector<pair<int, int>> anss;
		for (int i = 0; i < (1LL << n); i++) {
			pair<int, int> crnt = {0, 0};
			bool works = true;
			for (int j = 0; j < n; j++) {
				if ((i & (1LL << j))) {
					if (-crnt.first < valss[j].first) {
						crnt.first--;
						crnt.second += valss[j].second;
					}
					else {
						works = false;
						break;
					}
				}
			}
			if (!works) continue;
			anss.push_back(crnt);
		}
		sort(anss.begin(), anss.end());
		for (int i = 0; i < k; i++) {
			cout << -anss[i].first << ' ' << anss[i].second << '\n';
		}
	}
}

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