Submission #90818

#	Time	Username	Problem	Language	Result	Execution time	Memory
90818		YottaByte	Schools (IZhO13_school)	C++14	100 / 100	259 ms	19556 KiB

school

#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 (stderr)

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 / 100