Submission #17571

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
17571	2015-12-28T08:42:03 Z	gs14004	Schools (IZhO13_school)	C++14	65 / 100	2000 ms	18056 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];

multiset<pi> lev1, lev2;
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.insert(pi(a[i].first, a[i].second));
	}
	for(int i=m; i<n; i++){
		lev1.insert(pi(a[i].first, a[i].second));
	}
	for(int i=0; i<s; i++){
		int prof1 = -1e9, prof2 = -1e9, prof3 = -1e9;
		int add1 = 1e9, add2 = 1e9;
		pi pp1, pp2, pp3;
		for(auto &i : lev1){
			if(prof1 < i.second){ 
				prof1 = i.second;
				pp1 = i;
			}
			if(prof2 < i.first){ 
				prof2 = i.first;
				pp2 = i;
			}
		}
		for(auto &i : lev2){
			if(prof3 < i.second - i.first){
				prof3 = i.second - i.first;
				pp3 = i;
			}
		}
		if(prof1 >= prof2 + prof3){
			ret += prof1;
			lev1.erase(lev1.find(pp1));
		}
		else{
			ret += prof2 + prof3;
			lev2.erase(lev2.find(pp3));
			lev2.insert(pp2);
			lev1.erase(lev1.find(pp2));
		}
		// case 1. get s from empty set
		// case 2. get s from nonempty + get m from empty
		// case 3. swap s from empty set
	}
	cout<< ret;
}

Subtask #1

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4068 KB	Output is correct
2	Correct	0 ms	4068 KB	Output is correct
3	Correct	0 ms	4068 KB	Output is correct
4	Correct	0 ms	4068 KB	Output is correct
5	Correct	0 ms	4068 KB	Output is correct
6	Correct	0 ms	4068 KB	Output is correct
7	Correct	55 ms	4200 KB	Output is correct
8	Correct	8 ms	4200 KB	Output is correct
9	Correct	22 ms	4200 KB	Output is correct
10	Correct	10 ms	4200 KB	Output is correct
11	Correct	132 ms	4200 KB	Output is correct
12	Correct	141 ms	4200 KB	Output is correct
13	Correct	671 ms	5652 KB	Output is correct
14	Execution timed out	2000 ms	7628 KB	Program timed out
15	Execution timed out	2000 ms	11456 KB	Program timed out
16	Execution timed out	2000 ms	12380 KB	Program timed out
17	Execution timed out	2000 ms	14228 KB	Program timed out
18	Execution timed out	2000 ms	15284 KB	Program timed out
19	Execution timed out	2000 ms	16208 KB	Program timed out
20	Execution timed out	2000 ms	18056 KB	Program timed out