Submission #278745

#	Time	Username	Problem	Language	Result	Execution time	Memory
278745		Pbezz	Sure Bet (CEOI17_sure)	C++14	100 / 100	118 ms	5248 KiB

sure

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

#define loop(i,n) for (ll i = 0; i < n; i++)

#define ll long long
#define INF 100005
#define MOD 1000000007
#define pb push_back 
#define mp make_pair
typedef pair<ll,ll> pii;

const ll MAXN=1e6; 
ll a[MAXN+1];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	ll n,i,L;
	double k;
	cin>>n;
	double a[n+1],b[n+1];
	double Sa[n+1],Sb[n+1];

	Sa[0]=0; Sb[0]=0; a[0]=INF; b[0]=INF;

	for(i=1;i<=n;i++){

	cin>>a[i]>>b[i];
	}
	sort(a,a+n+1,greater<double>());
	sort(b,b+n+1,greater<double>());

	for(i=1;i<=n;i++){

	Sa[i]=Sa[i-1]+a[i];
	Sb[i]=Sb[i-1]+b[i];

		}

	double ans=0;

	for(i=1;i<=n;i++){//cout<<i<<" ";

	k=Sa[i];

	L=upper_bound(Sb,Sb+n+1,k)-Sb;

	//cout<<i<<" "<<k<<"  "<<L<<endl;

	if(L>1){

	k = Sb[L-1] -(L-1)-i;
	ans = max(ans,k);//cout<<k<<" ";
	}

	if(L!=n+1){

	k = Sa[i]-i-L;
	ans = max(ans,k);//cout<<k<<" ";

	}
//cout<<endl;

}

	printf("%.4lf\n",(double)ans);

return 0; 
}

/*
4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5

printf("%.4lf %.4lf\n",(double)a[i],(double)b[i]);
*/

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