oj.uz

답안 #90818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90818 2018-12-24T14:48:49 Z YottaByte 학교 설립 (IZhO13_school) C++14
100 / 100
 259 ms 19556 KB 
#include <bits/stdc++.h>

#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define int long long

using namespace std;

const int N = 3e5 + 5;

int n, x, y;

pair <int, int> a[N];

long long ans;

priority_queue < pair <int, int> > q1, q2; 

set <int> st;

main()
{
	cin >> n >> x >> y;
	
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &a[i].fr, &a[i].sc);
	}
	sort( a + 1, a + n + 1, greater < pair <int, int> >() );
	
	for (int i = 1; i <= x; i++)
		ans += a[i].fr, q1.push( mk(-a[i].fr + a[i].sc, i) );
		
	for (int i = x + 1; i <= n; i++)
		q2.push( mk(a[i].sc, i) ), st.insert(i);
	
	while(y--)
	{
		while (!q2.empty() && !st.count(q2.top().sc) )
			q2.pop();
			
		if ( q2.empty() || (!q1.empty() && q1.top().fr + a[*st.begin()].fr > q2.top().fr ) )
		{
			ans += q1.top().fr + a[*st.begin()].fr;
			q1.pop();
			q1.push( mk( -a[*st.begin() ].fr + a[*st.begin()].sc, *st.begin() ) );
			st.erase(st.begin());
		}
		else 
		{
			ans += q2.top().fr;
			st.erase( q2.top().sc );
			q2.pop();
		}
	}
	cout << ans << endl;
}
/**
5 3 2
25 40
25 17
34 6
24 6
32 4

12 4 8
15 43
15 4
33 6
10 20
28 45
20 44
47 26
10 36
15 37
11 7
24 41
45 39

**/

Compilation message

school.cpp:23:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
school.cpp: In function 'int main()':
school.cpp:29:35: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d%d", &a[i].fr, &a[i].sc);
                                   ^
school.cpp:29:35: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
school.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i].fr, &a[i].sc);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 536 KB Output is correct
7 Correct 4 ms 784 KB Output is correct
8 Correct 3 ms 840 KB Output is correct
9 Correct 3 ms 840 KB Output is correct
10 Correct 3 ms 840 KB Output is correct
11 Correct 5 ms 1012 KB Output is correct
12 Correct 5 ms 1012 KB Output is correct
13 Correct 14 ms 1852 KB Output is correct
14 Correct 58 ms 6968 KB Output is correct
15 Correct 103 ms 13236 KB Output is correct
16 Correct 259 ms 14000 KB Output is correct
17 Correct 178 ms 15524 KB Output is correct
18 Correct 171 ms 16060 KB Output is correct
19 Correct 207 ms 16672 KB Output is correct
20 Correct 247 ms 19556 KB Output is correct