oj.uz

Submission #65715

# Submission time Handle Problem Language Result Execution time Memory
65715 2018-08-08T13:15:06 Z polyfish Sure Bet (CEOI17_sure) C++14
20 / 100
 3 ms 712 KB 
//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 100002;

int n;
double A[MAX_N], B[MAX_N];

void enter() {
	cin >> n;
	for (int i=1; i<=n; ++i) {
		cin >> A[i] >> B[i];
	}
	sort(A+1, A+n+1);
	sort(B+1, B+n+1);
	reverse(A+1, A+n+1);
	reverse(B+1, B+n+1);
	for (int i=1; i<=n; ++i) {
		A[i] += A[i-1];
		B[i] += B[i-1];
	}
}

double bisect(int v) {
	int l = max(1, v-n), r = min(v, n);
	while (r-l+1>=3) {
		int mid1 = l + (r - l + 1) / 3;
		int mid2 = r - (r - l + 1) / 3;
		if (min(A[mid1], B[v-mid1]) > min(A[mid2], B[v-mid2]))
			r = mid2;
		else
			l = mid1;
	}
	double res = 0;
	for (int i=l; i<=r; ++i)
		res = max(res, min(A[i], B[v-i]));
	return res;
}

void solve() {
	double res = 0;
	//PR(A, n);
	//PR(B, n);
	//debug(bisect(5) - 5);
	for (int i=1; i<=2*n; ++i)
		res = max(res, bisect(i) - i);
	cout << setiosflags(ios::fixed) << setprecision(4) << res;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	solve();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Incorrect 3 ms 712 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Incorrect 3 ms 712 KB Output isn't correct
12 Halted 0 ms 0 KB -