Submission #1163485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163485		gelastropod	Akcija (COCI21_akcija)	C++20	0 / 110	18 ms	29252 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<int>> dp(n, vector<int>(n + 1, INT_MAX));
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			dp[0][0] = 0;
			int crntsum = 0;
			for (int j = 0; j < min((int)vals[i + 1].size(), i + 1); j++) {
				crntsum += vals[i + 1][j];
				dp[i][j + 1] = crntsum;
			}
			continue;
		}
		int crntsum = 0;
		dp[i][0] = 0;
		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++) {
				dp[i][k] = min(dp[i][k], dp[i - 1][k - j - 1] + crntsum);
			}
		}
		for (int j = 0; j <= n; j++) {
			dp[i][j] = min(dp[i][j], dp[i - 1][j]);
		}
	}
	for (int i = n; i >= 0; i--) {
		if (dp.back()[i] != INT_MAX) {
			cout << i << ' ' << dp.back()[i] << '\n';
			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