oj.uz

Submission #200175

# Submission time Handle Problem Language Result Execution time Memory
200175 2020-02-05T15:37:44 Z alishahali1382 Sure Bet (CEOI17_sure) C++14
100 / 100
 1451 ms 5344 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, LOG=20;

int n, m, k, u, v, x, y, t, a, b;
ld A[MAXN];
ld B[MAXN];

int get(ld val){
	if (val>min(A[n], B[n])) return inf;
	int x=lower_bound(A, A+n+1, val)-A;
	int y=lower_bound(B, B+n+1, val)-B;
	return x+y;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	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=2; i<=n; i++) A[i]+=A[i-1], B[i]+=B[i-1];
	
	ld ans=0;
	for (int i=1; i<=2*n; i++){
		ld dwn=0, up=1e8;
		for (int j=0; j<50; j++){
			ld mid=(dwn+up)/2;
			if (get(mid)>i) up=mid;
			else dwn=mid;
		}
		ans=max(ans, dwn-i);
	}
	cout<<setprecision(4)<<fixed<<ans<<'\n';
	
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 5 ms 380 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 13 ms 376 KB Output is correct
13 Correct 19 ms 376 KB Output is correct
14 Correct 13 ms 376 KB Output is correct
15 Correct 16 ms 376 KB Output is correct
16 Correct 14 ms 376 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 5 ms 380 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 13 ms 376 KB Output is correct
13 Correct 19 ms 376 KB Output is correct
14 Correct 13 ms 376 KB Output is correct
15 Correct 16 ms 376 KB Output is correct
16 Correct 14 ms 376 KB Output is correct
17 Correct 1199 ms 4984 KB Output is correct
18 Correct 1265 ms 4888 KB Output is correct
19 Correct 1228 ms 4960 KB Output is correct
20 Correct 1139 ms 4892 KB Output is correct
21 Correct 1386 ms 5344 KB Output is correct
22 Correct 1266 ms 4892 KB Output is correct
23 Correct 1336 ms 4892 KB Output is correct
24 Correct 1294 ms 4896 KB Output is correct
25 Correct 1217 ms 4896 KB Output is correct
26 Correct 1451 ms 5268 KB Output is correct