oj.uz

답안 #92797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92797 2019-01-04T21:02:03 Z luciocf 학교 설립 (IZhO13_school) C++14
100 / 100
 401 ms 31352 KB 
#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

# 결과 실행 시간 메모리 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