제출 #1163528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163528		gelastropod	Akcija (COCI21_akcija)	C++20	0 / 110	348 ms	63368 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}));
	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 = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << dp[i][j].first << ' ' << dp[i][j].second << ' ';
		}
		cout << '\n';
	}*/
	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;
		}
	}
}

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