Submission #90802

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90802	2018-12-24T13:16:25 Z	YottaByte	Schools (IZhO13_school)	C++14	0 / 100	331 ms	25408 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	376 KB	Output isn't correct
3	Incorrect	2 ms	636 KB	Output isn't correct
4	Incorrect	2 ms	636 KB	Output isn't correct
5	Incorrect	2 ms	636 KB	Output isn't correct
6	Incorrect	2 ms	636 KB	Output isn't correct
7	Incorrect	6 ms	1068 KB	Output isn't correct
8	Incorrect	5 ms	1208 KB	Output isn't correct
9	Incorrect	5 ms	1208 KB	Output isn't correct
10	Incorrect	5 ms	1208 KB	Output isn't correct
11	Incorrect	6 ms	1208 KB	Output isn't correct
12	Incorrect	6 ms	1208 KB	Output isn't correct
13	Incorrect	30 ms	3744 KB	Output isn't correct
14	Incorrect	79 ms	6932 KB	Output isn't correct
15	Incorrect	161 ms	13160 KB	Output isn't correct
16	Incorrect	174 ms	14888 KB	Output isn't correct
17	Incorrect	222 ms	17896 KB	Output isn't correct
18	Incorrect	244 ms	19616 KB	Output isn't correct
19	Incorrect	269 ms	21096 KB	Output isn't correct
20	Incorrect	331 ms	25408 KB	Output isn't correct