Submission #1176545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176545		Dan4Life	Sure Bet (CEOI17_sure)	C++20	100 / 100	70 ms	1864 KiB

sure

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

const int mxN = (int)1e5+10;
int n;
double a[2][mxN], ans;

double f(int i, int j){
	return min(a[0][i]-(j+1),a[1][j]-(i+1));
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[0][i] >> a[1][i];
		a[0][i]--, a[1][i]--;
	}
	for(int j : {0,1}){
		sort(a[j],a[j]+n); reverse(a[j],a[j]+n);
		for(int i = 1; i < n; i++) a[j][i]+=a[j][i-1];
	}
	for(int i = 0; i < n; i++){
		int l = 0, r = n-1;
		while(r-l>3){
			int third = (r-l)/3;
			if(f(i,l+third)<f(i,r-third))l+=third;
			else r-=third;
		}
		for(int j = l; j <= r; j++) ans=max(ans,f(i,j));
	}
	cout << fixed << setprecision(4) << ans << "\n";
}

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