oj.uz

답안 #90761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90761 2018-12-24T10:30:34 Z YottaByte 학교 설립 (IZhO13_school) C++14
15 / 100
 2000 ms 35800 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;
	
	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()
      ^
school.cpp: In function 'int main()':
school.cpp:74:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = n - m - s;
      ^~~

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Incorrect 2 ms 508 KB Output isn't correct
5 Incorrect 2 ms 512 KB Output isn't correct
6 Incorrect 2 ms 524 KB Output isn't correct
7 Incorrect 6 ms 1128 KB Output isn't correct
8 Incorrect 28 ms 1264 KB Output isn't correct
9 Incorrect 18 ms 1264 KB Output isn't correct
10 Incorrect 10 ms 1264 KB Output isn't correct
11 Incorrect 8 ms 1264 KB Output isn't correct
12 Incorrect 6 ms 1264 KB Output isn't correct
13 Incorrect 794 ms 4912 KB Output isn't correct
14 Incorrect 428 ms 9832 KB Output isn't correct
15 Incorrect 203 ms 17160 KB Output isn't correct
16 Execution timed out 2047 ms 21828 KB Time limit exceeded
17 Execution timed out 2037 ms 26372 KB Time limit exceeded
18 Execution timed out 2055 ms 29016 KB Time limit exceeded
19 Execution timed out 2033 ms 31236 KB Time limit exceeded
20 Execution timed out 2041 ms 35800 KB Time limit exceeded