Submission #1027331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027331		vjudge1	Sure Bet (CEOI17_sure)	C++98	100 / 100	95 ms	6740 KiB

sure

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//#pragma GCC target("arch=skylake")

//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("arch=skylake")
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
#define el cout << '\n';
//#define float long double
#define MASK(i) (1LL << (i))
//#define c_bit(i) __builtin_popcountll(i) // dem so bit dang bat
#define BIT(x, i) ((x) & MASK(i)) // trang thai bit i trong x
//#define SET_ON(x, i) ((x) | MASK(i)) // b?t bit i trong x
//#define SET_OFF(x, i) ((x) & ~MASK(i)) // tat bit i trong x
using namespace std;

const int N = 1e5+5;
const int inf = 1e18;
const int mod = 1e9+7;
const int limit = 3e6;
const int S = 350;

int n;


void solve(){
    cin>>n;
    long double a[n+5],b[n+5];
    long double pr1[n+5],pr2[n+5];
    for(int i=1; i<=n;i++){
    	cin>>a[i];
    	cin>>b[i];
	}
//	for(int i=1; i<=n; i++){
//		cout << a[i] << ' ' << b[i] << '\n';
//	}
	sort(a+1,a+1+n);sort(b+1,b+1+n);
//	for(int i=1; i<=n; i++){
//		cout << a[i] << ' ' << b[i] << '\n';
//	}
//	el;
	pr1[0]=0;pr2[0]=0;
	for(int i=1; i<=n; i++){
		pr1[i] = pr1[i-1] + a[n-i+1];
		pr2[i] = pr2[i-1] + b[n-i+1];
		//cout << pr1[i] << ' ' << pr2[i] << '\n';
	}
	long double ans = 0;
//	int l=1,r=n;
	for(int i=0; i<=n; i++){
		int l=0,r=n;
	    while(l<=r){
		int m1 = l+(r-l)/3;
		int m2 = r-(r-l)/3;
	    long double t1 = min((long double)pr1[i] - i -m1, (long double)pr2[m1]-i-m1);
		long double t2 = min((long double)pr1[i] - i-m2 , (long double)pr2[m2]-i-m2);
	//	cout <<  t1 << ' ' << t2 << '\n';
		if(t1<t2){
			ans = max(ans,t2);
			l=m1+1;
		}
		else {
			ans = max(ans , t1);
			r=m2-1;
		}
    }
	}
	cout << fixed << setprecision(4) << ans;
}

signed main(){
	// freopen("MAXSQR.INP", "r", stdin);
	 //freopen("MAXSQR.OUT", "w", stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);  
	int t=1;
    //cin>>t;
	while(t--){
	solve();el;
	//tuab
}  
}

// 23
// 10111
// 10110
// 10101
// 10011
// 00111
                                                      

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