제출 #617163

#제출 시각아이디문제언어결과실행 시간메모리
617163cfalasSure Bet (CEOI17_sure)C++17
100 / 100
175 ms4368 KiB
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second

#define ll long long
#define FORi(i,a,b) for(ll i=a;i<(ll)b;i++)
#define FOR(i,n) FORi(i,0,n)
#define FOA(v,a) for(auto v : a)
#define MID ((l+r)/2)

int n;
vector<double> a, b;

int main(){
	cin>>n;
	a.resize(n);
	b.resize(n);
	FOR(i,n) cin>>a[i]>>b[i];
	sort(a.begin(), a.end(), [](double a, double b){return a>b;});
	sort(b.begin(), b.end(), [](double a, double b){return a>b;});

	double ans=0;
	double sa=0;

	double sb[n];
	sb[0] = b[0];
	FORi(i,1,n) sb[i] = sb[i-1] + b[i];
	FOR(i,n){
		sa+=a[i];
		int nxt = lower_bound(sb, sb+n, sa)-sb;
		if(nxt!=n+1)
			ans = max(ans, min(sb[nxt]-i-1-nxt-1, sa-nxt-1-i-1));
		if(nxt!=0){
			nxt--;
			ans = max(ans, min(sb[nxt]-i-1-nxt-1, sa-nxt-1-i-1));
		}
	}
	cout<<fixed<<setprecision(4)<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...