Submission #43950

#	Time	Username	Problem	Language	Result	Execution time	Memory
43950		sorry_Benq	Sure Bet (CEOI17_sure)	C++17	100 / 100	224 ms	18412 KiB

sure

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

double A[100005];
double B[100005];
double X[100005];
double Y[100005];
int main(){
	int N; cin >> N; 
	for (int i = 1; i <= N; i++){
		cin >> A[i] >> B[i];
	}
	
	sort(A, A + N + 1);
	sort(B, B + N + 1);
	
	for (int i = 1; i <= N; i++){
		X[i] = X[i - 1] + (A[N - i + 1] - 1);
		Y[i] = Y[i - 1] + (B[N - i + 1] - 1);
	}
	double lo = 0;
	double hi = 1e9;
	for (int x = 0; x <= 70; x++){
		double mid = (lo + hi)/2;
		bool fnd = false;
	
		for (int i = 1; i <= N; i++){
			double y = X[i] - mid;
			int k = (int) y;
			if (k < 0){
				continue;
			}
			if (k >= N){
				k = N;
			}
			if (Y[k] - i >= mid) fnd = true;
		}
		if (!fnd) hi = mid;
		else{
			lo = mid;
		}
	}
	printf("%.4lf", lo); 
}

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