/* Speech to the young */
//#include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
/*
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse,-fgcse-lm")
#pragma GCC optimize("-ftree-pre,-ftree-vrp")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
*/
using namespace std;
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)
#define int long long
#define cube (x) ((x) * (x) * (x))
int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
void pre(int a) { cout<<fixed<<setprecision(a); }
int bitcount (int x) {return __builtin_popcount (x);}
const int N = 2e6 + 10;
const int INF = 1e18 + 1;
const int MOD = 1e9 + 7;
const int P = 31;
const double eps = 1e-19;
long double pi = 3.1415926535897323;
double a[N], b[N], res, suma[N], sumb[N];
int n;
void Solution () {
cin >> n;
for (int i = 1; i <= n; ++ i) cin >> a[i] >> b[i];
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) {
suma[i] = suma[i - 1] + a[i];
sumb[i] = sumb[i - 1] + b[i];
}
for (int i = 1; i <= n; ++ i) {
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (sumb[mid] >= suma[i]) {
r = mid - 1;
ans = mid;
} else l = mid + 1;
}
if (ans != -1) res = max (res, (double)(suma[i] - (double)(ans + i)));
}
for (int i = 1; i <= n; ++ i) {
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (suma[mid] >= sumb[i]) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
if (ans != -1) res = max (res, (double)(sumb[i] - (double)(ans + i)));
}
cout << fixed << setprecision (4) << res;
return;
}
signed main () {
YOSIK();
// precalc();
int T = 1;
// cin >> T;
while (T --) Solution ();
exit (0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
77 ms |
3464 KB |
Output is correct |
18 |
Correct |
78 ms |
4796 KB |
Output is correct |
19 |
Correct |
76 ms |
4752 KB |
Output is correct |
20 |
Correct |
74 ms |
4792 KB |
Output is correct |
21 |
Correct |
83 ms |
5092 KB |
Output is correct |
22 |
Correct |
77 ms |
4792 KB |
Output is correct |
23 |
Correct |
78 ms |
4728 KB |
Output is correct |
24 |
Correct |
76 ms |
4824 KB |
Output is correct |
25 |
Correct |
78 ms |
4828 KB |
Output is correct |
26 |
Correct |
83 ms |
5184 KB |
Output is correct |