Submission #92797

#	Time	Username	Problem	Language	Result	Execution time	Memory
92797		luciocf	Schools (IZhO13_school)	C++14	100 / 100	401 ms	31352 KiB

school

#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;

const int maxn = 3e5+10;

typedef pair<int, int> pii;

typedef long long ll;

pii num[maxn];

bool comp(pii a, pii b){return a.first > b.first;}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie();

	int n, m, s;
	cin >> n >> m >> s;

	for (int i = 1; i <= n; i++)
		cin >> num[i].first >> num[i].second;

	sort(num+1, num+n+1, comp);

	multiset< pair<int, pii>, greater< pair<int, pii > > > choose; // a was chosen
	multiset< pii, greater<pii> > free_a, free_b; // pairs unchosen, ordered by a, then b

	ll ans = 0LL;
	for (int i = 1; i <= m; i++)
	{
		ans += num[i].first;
		choose.insert({num[i].second-num[i].first, {num[i].first, num[i].second}});
	}

	for (int i = m+1; i <= n; i++)
	{
		free_a.insert({num[i].first, num[i].second});
		free_b.insert({num[i].second, num[i].first});
	}

	// pretty confusing
	for (int i = 1; i <= s; i++)
	{
		int x = (*choose.begin()).ff+(*free_a.begin()).ff;
		int y = (*free_b.begin()).ff;

		if (x > y)
		{
			ans += x, choose.erase(choose.begin());

			int a = (*free_a.begin()).ff;
			int b = (*free_a.begin()).ss;

			choose.insert({b-a, {a, b}});

			free_a.erase(free_a.begin());
			free_b.erase(free_b.find({b, a}));
		}
		else
		{
			ans += y;

			int a = (*free_b.begin()).ss;
			int b = (*free_b.begin()).ff;

			free_a.erase(free_a.find({a, b}));
			free_b.erase(free_b.begin());
		}
	}

	cout << ans << "\n";
}

• Subtask 1: 100 / 100