Submission #90782

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90782	2018-12-24T11:34:15 Z	YottaByte	Schools (IZhO13_school)	C++14	0 / 100	2000 ms	35720 KB

school

#include <iostream>
#include <queue>

using namespace std;

#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define ll long long
#define int long long
#define pii pair < int, int >

const int N = 3e5 + 1;

priority_queue < pair < int, pii > > v;
priority_queue < pair < int, pii > > vm;
priority_queue < pair < int, pii >, vector < pair < int, pii > >, greater < pair < int, pii > > > pq;
ll ans;
int u[N], um[N], us[N], ii;

int maxim()
{
	int id = vm.top().sc.sc;
	int res = vm.top().fr;
	if(!vm.size())
	{
		return -1e11;
	}
	while(u[id] && vm.size())
	{
		vm.pop();
		id = vm.top().sc.sc;
		res = vm.top().fr;
	}
	
	ii = id;
	return res;
}

int maxs(priority_queue < pair < int, pii > > temp)
{
	int id = temp.top().sc.sc;
	int res = temp.top().fr;

	if(!temp.size())
	{
		return 1e11;
	}
	
	while(u[id] && temp.size())
	{
		temp.pop();
		id = temp.top().sc.sc;
		res = temp.top().fr;
	}
	
	return res;
}

main()
{
	int n, m, s;
	cin >> n >> m >> s;
	for(int i = 1; i <= n; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push( { b, {a, i} } );
		vm.push( { a, {b, i} } );
		pq.push( { a, {b, i} } );
	}
	
	int cnt = n - m - s;
	if(m + s == n)
	{
		while(s--)
		{
			int mx = v.top().fr, id = v.top().sc.sc;
			
			v.pop();
			
			u[id] = 1;
			
			//cout << id + 1 << endl;
			
			u[id] = 1;
			ans += mx;
		}
		
		while(cnt)
		{
			int id = pq.top().sc.sc;
			int mn = pq.top().fr;
			pq.pop();
			
			if(u[id]) continue;
			
		//puts("Del");
			//cout << id + 1 << endl;
			
			cnt--;
			u[id] = 1;
			ans -= mn;
		}
	}
	else
	{
		while(m--)
		{
			int mx = vm.top().fr;
			int id = vm.top().sc.sc;
			us[id] = vm.top().sc.fr;
			vm.pop();
			
			u[id] = 1;
			um[id] = mx;
			
			ans += mx;
		}
		
		while(s)
		{
			int mx = v.top().fr;
			int id = v.top().sc.sc;
			v.pop();
			
			if(um[id])
			{
				int mxm = maxim();
				int tmp = ans + us[id] - um[id] + mxm;
				
				mx = maxs(v);
				if(ans + mx < tmp)
				{
					ans = tmp;
					s--;
					u[ii] = 1;
					um[ii] = mxm;
					us[ii] = mx;
					if(vm.size())
						vm.pop();
				}
			}
			else
			{
				u[id] = 1;
				ans += mx;
				s--;
			}
		}
	}
	
	cout << ans << endl;
}
/*
3 1 1
5 2
4 1
6 4

7 2 3
9 8
10 6
3 5
1 7
5 7
6 3
5 4

4 1 1
6 16
2 14
4 5
15 19
*/

Compilation message

school.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Incorrect	2 ms	508 KB	Output isn't correct
3	Incorrect	1 ms	508 KB	Output isn't correct
4	Incorrect	2 ms	508 KB	Output isn't correct
5	Incorrect	2 ms	508 KB	Output isn't correct
6	Incorrect	2 ms	508 KB	Output isn't correct
7	Incorrect	14 ms	1044 KB	Output isn't correct
8	Incorrect	5 ms	1116 KB	Output isn't correct
9	Incorrect	17 ms	1116 KB	Output isn't correct
10	Incorrect	10 ms	1116 KB	Output isn't correct
11	Incorrect	7 ms	1116 KB	Output isn't correct
12	Incorrect	6 ms	1144 KB	Output isn't correct
13	Incorrect	772 ms	4872 KB	Output isn't correct
14	Incorrect	430 ms	9916 KB	Output isn't correct
15	Incorrect	124 ms	17080 KB	Output isn't correct
16	Incorrect	166 ms	17080 KB	Output isn't correct
17	Execution timed out	2061 ms	26648 KB	Time limit exceeded
18	Execution timed out	2069 ms	28848 KB	Time limit exceeded
19	Execution timed out	2066 ms	31152 KB	Time limit exceeded
20	Execution timed out	2073 ms	35720 KB	Time limit exceeded