oj.uz

Submission #46294

# Submission time Handle Problem Language Result Execution time Memory
46294 2018-04-19T01:12:15 Z RezwanArefin01 Sure Bet (CEOI17_sure) C++17
100 / 100
 209 ms 15364 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e5 + 10; 
double a[N], b[N];

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n; cin >> n; 
	for(int i = 1; i <= n; i++) 
		cin >> a[i] >> b[i];
	sort(a + 1, a + n + 1, greater<double>());
	sort(b + 1, b + n + 1, greater<double>()); 
	for(int i = 1; i <= n; i++) 
		a[i] += a[i - 1], b[i] += b[i - 1];

	double ans = 0; 
	for(int i = 0; i <= n; i++) {
		int lo = 0, hi = n; 
		while(lo <= hi) {
			int m1 = lo + (hi - lo) / 3; 
			int m2 = hi - (hi - lo) / 3; 
			double f1 = min(a[i], b[m1]) - i - m1; 
			double f2 = min(a[i], b[m2]) - i - m2;
			ans = max({ans, f1, f2}); 
			if(f1 < f2) lo = m1 + 1; 
			else hi = m2 - 1; 
		}
	}
	cout << fixed << setprecision(4) << ans << endl;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 536 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 2 ms 644 KB Output is correct
12 Correct 3 ms 644 KB Output is correct
13 Correct 5 ms 644 KB Output is correct
14 Correct 7 ms 644 KB Output is correct
15 Correct 3 ms 644 KB Output is correct
16 Correct 4 ms 644 KB Output is correct
17 Correct 183 ms 2304 KB Output is correct
18 Correct 177 ms 3452 KB Output is correct
19 Correct 179 ms 4964 KB Output is correct
20 Correct 181 ms 6252 KB Output is correct
21 Correct 197 ms 8024 KB Output is correct
22 Correct 184 ms 9408 KB Output is correct
23 Correct 182 ms 10776 KB Output is correct
24 Correct 188 ms 12160 KB Output is correct
25 Correct 183 ms 13528 KB Output is correct
26 Correct 209 ms 15364 KB Output is correct