Submission #237811

#	Time	Username	Problem	Language	Result	Execution time	Memory
237811		eohomegrownapps	Sure Bet (CEOI17_sure)	C++14	100 / 100	140 ms	11512 KiB

sure

#include <bits/stdc++.h>
using namespace std;

typedef long double ld;

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	vector<ld> vals1(n);
	vector<ld> vals2(n);
	vector<ld> pref1(n+1);
	vector<ld> pref2(n+1);
	vector<ld> prefind1(n+1);
	vector<ld> prefind2(n+1);
	for (int i = 0; i<n; i++){
		cin>>vals1[i]>>vals2[i];
	}
	sort(vals1.rbegin(),vals1.rend());
	sort(vals2.rbegin(),vals2.rend());
	for (int i = 1; i<=n; i++){
		pref1[i]=pref1[i-1]+vals1[i-1]-1;
		prefind1[i]=pref1[i]+i;
		pref2[i]=pref2[i-1]+vals2[i-1]-1;
		prefind2[i]=pref2[i]+i;
	}
	ld maxval = 0;
	for (int i = 0; i<=n; i++){
		//smallest x such that prefind1[i]<prefind2[x]
		//cout<<"x "<<i<<'\n';
		int lb = lower_bound(prefind2.begin(),prefind2.end(),prefind1[i])-prefind2.begin();
		//cout<<lb<<'\n';
		if (lb!=n+1){maxval=max(maxval,pref1[i]-lb);}
		int ub = lb-1;
		//cout<<ub<<'\n';
		if (ub!=-1){maxval=max(maxval,pref2[ub]-i);}
	}
	cout<<fixed<<setprecision(4)<<maxval<<'\n';
}

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