Submission #1009194

#TimeUsernameProblemLanguageResultExecution timeMemory
1009194lrancicSchools (IZhO13_school)C++17
15 / 100
136 ms7160 KiB
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<bool> city;

long long solve(int n, int m, int s, std::vector<std::pair<int, int>> &music, std::vector<std::pair<int, int>> &sports, int i = 0, long long c = 0LL) {
	if (i >= n) return c;

	for (; i < n; i++) {
		if (music[i].second == sports[i].second && m > 0 && s > 0) {
			city[music[i].second] = true;
			return std::max(solve(n, m-1, s, music, sports, i+1, c+music[i].first), solve(n, m, s-1, music, sports, i+1, c+sports[i].first));
		}

		if (m > 0 && !city[music[i].second]) { c += music[i].first; m--; city[music[i].second] = true; }
		if (s > 0 && !city[sports[i].second]) { c += sports[i].first; s--; city[sports[i].second] = true; }

		if (m < 1 && s < 1) return c;
	}

	return c;
}

int main() {
	int n, m, s; std::cin >> n >> m >> s;
	std::vector<std::pair<int, int>> music(n), sports(n);
	for (int i = 0; i < n; i++) { std::cin >> music[i].first >> sports[i].first; music[i].second = sports[i].second = i; city.push_back(false); }

	// for (std::pair<int, int> i : music) std::cout << i.first << ' ' << i.second << '\t';
	// std::cout << '\n'; 
	// for (std::pair<int, int> i : sports) std::cout << i.first << ' ' << i.second << '\t';
	// std::cout << '\n'; 

	std::sort(sports.begin(), sports.end(), std::greater<std::pair<int, int>>()); std::sort(music.begin(), music.end(), std::greater<std::pair<int, int>>());
	std::cout << solve(n, m, s, music, sports) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...