oj.uz

답안 #17571

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17571 2015-12-28T08:42:03 Z gs14004 학교 설립 (IZhO13_school) C++14
65 / 100
 2000 ms 18056 KB 
#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

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