Submission #92797

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92797	2019-01-04T21:02:03 Z	luciocf	Schools (IZhO13_school)	C++14	100 / 100	401 ms	31352 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	5 ms	888 KB	Output is correct
8	Correct	4 ms	760 KB	Output is correct
9	Correct	4 ms	760 KB	Output is correct
10	Correct	4 ms	760 KB	Output is correct
11	Correct	6 ms	920 KB	Output is correct
12	Correct	6 ms	844 KB	Output is correct
13	Correct	23 ms	3320 KB	Output is correct
14	Correct	81 ms	8888 KB	Output is correct
15	Correct	217 ms	18400 KB	Output is correct
16	Correct	338 ms	19980 KB	Output is correct
17	Correct	283 ms	22540 KB	Output is correct
18	Correct	305 ms	24712 KB	Output is correct
19	Correct	339 ms	27000 KB	Output is correct
20	Correct	401 ms	31352 KB	Output is correct