Submission #711140

#TimeUsernameProblemLanguageResultExecution timeMemory
711140WonderfulWhaleSure Bet (CEOI17_sure)C++17
100 / 100
111 ms7704 KiB
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	vector<pair<double, double>> v1, v2;
	for(int i=0;i<n;i++) {
		double x, y;
		cin >> x >> y;
		v1.pb({-x, -y});
		v2.pb({-y, -x});
	}
	sort(all(v1));
	sort(all(v2));
	vector<double> pre1, pre2;
	for(int i=0;i<n;i++) {
		pre1.pb(-v1[i].st+(i?pre1[i-1]:0));
		pre2.pb(-v2[i].st+(i?pre2[i-1]:0));
	}
	double ans = 0;
	for(int i=0;i<n;i++) {
		int s = -1;
		int e = n;
		while(e-s>1) {
			int m = (e+s)/2;
			if(pre2[m]>=pre1[i]) e = m;
			else s = m;
		}
		if(e == n) continue;
		ans = max(ans, pre1[i]-i-1-e-1);
	}
	for(int i=0;i<n;i++) {
		int s = -1;
		int e = n;
		while(e-s>1) {
			int m = (e+s)/2;
			if(pre1[m]>=pre2[i]) e = m;
			else s = m;
		}
		if(e == n) continue;
		ans = max(ans, pre2[i]-i-1-e-1);
	}
	printf("%.4lf",(double)ans);
	cout << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...