oj.uz

답안 #90782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90782 2018-12-24T11:34:15 Z YottaByte 학교 설립 (IZhO13_school) C++14
0 / 100
 2000 ms 35720 KB 
#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

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