Submission #47230

#	Time	Username	Problem	Language	Result	Execution time	Memory
47230		robert	Sure Bet (CEOI17_sure)	C++14	100 / 100	171 ms	17932 KiB

sure

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef vector<double> vd;

vd a, b;

int main(){
	iostream::sync_with_stdio(0); cin.tie(0);
	int N; cin>>N;
	for(int n=0; n<N; n++){
		a.push_back(0);
		b.push_back(0);
		cin>>a[n]>>b[n];
	}
	sort(a.rbegin(), a.rend());
	sort(b.rbegin(), b.rend());
	double opt = 0.0;
	double sm = 0.0;
	vd pf; pf.assign(N, 0.0);
	pf[0] = b[0];
	for(int y=1; y<N; y++){
		pf[y] = b[y]+pf[y-1];
	}
	for(int x=0; x<N; x++){
		sm += a[x];
		//here we need to find the least point where sm2>=sm, then the answer is either that or the highest point where sm>sm2
		int l = 0, r = N-1;
		while(l!=r){
			int m = (l+r)/2;
			if(pf[m]>=sm){
				//sm2>sm
				r = m;
			} else {
				l = m+1;
			}
		}
		if(l>0)
			opt = max(max(min(sm-(x+l+2), pf[l]-(x+l+2)), min(sm-(x+l+1), pf[l-1]-(x+l+1))), opt);
		else
			opt = max(opt, min(sm-(x+l+2), pf[l]-(x+l+2)));
	}
	printf("%.4lf", opt);
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40