oj.uz

Submission #56794

# Submission time Handle Problem Language Result Execution time Memory
56794 2018-07-12T15:01:44 Z youngyojun Sure Bet (CEOI17_sure) C++11
100 / 100
 182 ms 16964 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;

const ld EPS = 1e-9;
const int MAXN = 100005;

ll A[MAXN], B[MAXN];

ll Ans;
int N;

ll f(int a, int b) {
	return min(A[a], B[b]);
}

ll getAns(int X) {
	int s = max(1, X-N), e = min(N, X-1);
	for(int m; s < e;) {
		m = (s+e)/2;
		ll t1 = f(m, X-m), t2 = f(m+1, X-m-1);
		if(t1 < t2) s = m+1;
		else e = m;
	}
	return f(s, X-s);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) {
		ld a, b; cin >> a >> b;
		A[i] = a*10000 + EPS;
		B[i] = b*10000 + EPS;
	}

	sort(A+1, A+N+1); reverse(A+1, A+N+1);
	sort(B+1, B+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];
	}

	for(int i = 2; i <= N*2; i++)
		upmax(Ans, getAns(i) - ll(i)*10000);
	
	printf("%.4Lf\n", ld(Ans)/10000 + EPS);
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 548 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 4 ms 568 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 548 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 4 ms 568 KB Output is correct
7 Correct 3 ms 576 KB Output is correct
8 Correct 3 ms 580 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 5 ms 740 KB Output is correct
13 Correct 4 ms 740 KB Output is correct
14 Correct 4 ms 824 KB Output is correct
15 Correct 5 ms 824 KB Output is correct
16 Correct 4 ms 824 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 548 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 4 ms 568 KB Output is correct
7 Correct 3 ms 576 KB Output is correct
8 Correct 3 ms 580 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 5 ms 740 KB Output is correct
13 Correct 4 ms 740 KB Output is correct
14 Correct 4 ms 824 KB Output is correct
15 Correct 5 ms 824 KB Output is correct
16 Correct 4 ms 824 KB Output is correct
17 Correct 143 ms 3756 KB Output is correct
18 Correct 157 ms 5292 KB Output is correct
19 Correct 153 ms 6520 KB Output is correct
20 Correct 182 ms 7972 KB Output is correct
21 Correct 156 ms 9672 KB Output is correct
22 Correct 178 ms 10968 KB Output is correct
23 Correct 162 ms 12416 KB Output is correct
24 Correct 142 ms 13804 KB Output is correct
25 Correct 167 ms 15128 KB Output is correct
26 Correct 156 ms 16964 KB Output is correct