Submission #17574

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
17574	2015-12-28T09:02:14 Z	gs14004	Schools (IZhO13_school)	C++14	100 / 100	175 ms	13076 KB

school

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n, m, s;
pi a[300005];

struct node{
	int x, y, i;
};

auto func1 = [](const node &a, const node &b){
	if(a.x != b.x) return a.x < b.x;
	return a.y > b.y;
};

auto func2 = [](const node &a, const node &b){
	if(a.y != b.y) return a.y < b.y;
	return a.x > b.x;
};

priority_queue<node, vector<node>, decltype(func1) > pq1 (func1);
priority_queue<node, vector<node>, decltype(func2) > pq2 (func2);
priority_queue<int> lev2;

bool inque[300005];

int main(){
	cin >> n >> m >> s;
	for(int i=0; i<n; i++){
		scanf("%d %d",&a[i].first, &a[i].second);
	}
	sort(a, a+n);
	reverse(a, a+n);
	lint ret = 0;
	for(int i=0; i<m; i++){
		ret += a[i].first;
		lev2.push(a[i].second - a[i].first);
	}
	for(int i=m; i<n; i++){
		inque[i] = 1;
		pq1.push({a[i].first, a[i].second, i});
		pq2.push({a[i].first, a[i].second, i});
	}
	for(int i=0; i<s; i++){
		while(!inque[pq1.top().i]) pq1.pop();
		while(!inque[pq2.top().i]) pq2.pop();
		node p1 = pq1.top(), p2 = pq2.top();
		if(p2.y >= p1.x + lev2.top()){
			ret += p2.y;
			inque[p2.i] = 0;
		}
		else{
			ret += p1.x + lev2.top();
			inque[p1.i] = 0;
			lev2.pop();
			lev2.push(p1.y - p1.x);
		}
		// case 1. get s from empty set
		// case 2. get s from nonempty + get m from empty
	}
	cout<< ret;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4360 KB	Output is correct
2	Correct	1 ms	4360 KB	Output is correct
3	Correct	0 ms	4360 KB	Output is correct
4	Correct	0 ms	4360 KB	Output is correct
5	Correct	0 ms	4360 KB	Output is correct
6	Correct	0 ms	4360 KB	Output is correct
7	Correct	2 ms	4524 KB	Output is correct
8	Correct	0 ms	4360 KB	Output is correct
9	Correct	2 ms	4360 KB	Output is correct
10	Correct	0 ms	4360 KB	Output is correct
11	Correct	0 ms	4524 KB	Output is correct
12	Correct	2 ms	4684 KB	Output is correct
13	Correct	8 ms	4716 KB	Output is correct
14	Correct	46 ms	8336 KB	Output is correct
15	Correct	84 ms	12240 KB	Output is correct
16	Correct	159 ms	12372 KB	Output is correct
17	Correct	136 ms	13076 KB	Output is correct
18	Correct	141 ms	13076 KB	Output is correct
19	Correct	116 ms	13076 KB	Output is correct
20	Correct	175 ms	13076 KB	Output is correct