Submission #17569

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
17569	2015-12-28T08:06:53 Z	gs14004	Schools (IZhO13_school)	C++14	55 / 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, tret = 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));
	}
	tret = ret;
	for(int i=0; i<s; i++){
		int prof1 = -1e9, prof2 = -1e9, prof3 = -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(pp1);
		}
		else{
			ret += prof2 + prof3;
			lev2.erase(pp3);
			lev2.insert(pp2);
			lev1.erase(pp2);
		}
		tret = max(tret, ret);
		// case 1. get s from empty set
		// case 2. get s from nonempty + get m from empty
		// case 3. 
	}
	cout<< tret;
}

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	4068 KB	Output isn't correct
2	Correct	0 ms	4068 KB	Output is correct
3	Correct	0 ms	4068 KB	Output is correct
4	Incorrect	0 ms	4068 KB	Output isn't correct
5	Correct	0 ms	4068 KB	Output is correct
6	Correct	0 ms	4068 KB	Output is correct
7	Correct	53 ms	4200 KB	Output is correct
8	Correct	4 ms	4200 KB	Output is correct
9	Correct	19 ms	4200 KB	Output is correct
10	Correct	5 ms	4200 KB	Output is correct
11	Correct	140 ms	4200 KB	Output is correct
12	Correct	148 ms	4200 KB	Output is correct
13	Correct	658 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