This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e6 + 1;
void solve() {
int n;
cin >> n;
double a[n], b[n], a0[n], b0[n], ans = 0;
for(int i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
sort(a, a + n), sort(b, b + n);
for(int i = 0; i < n; i++){
a0[i] = a[i] - 2;
b0[i] = b[i] - 2;
a[i]--, b[i]--;
if(i)a[i] += a[i - 1], b[i] += b[i - 1];
}
double s = 0, t = 0;
for(int i = n - 1; i >= 0; i--){
s += a0[i], t += b0[i];
ans = max(ans, min(s, t));
int l = -1, r = i;
if(s < t){
while(l + 1 < r){
int mid = l + (r - l) / 2;
if(t - (i - mid) > s + (i ? a[i - 1] : 0) - (mid ? a[mid - 1] : 0))r = mid;
else l = mid;
}
ans = max(ans, s + (i ? a[i - 1] : 0) - (r ? a[r - 1] : 0));
if(r)ans = max(ans, t - (i - r) - 1);
}
else if(s > t){
while(l + 1 < r){
int mid = l + (r - l) / 2;
if(s - (i - mid) > t + (i ? b[i - 1] : 0) - (mid ? b[mid - 1] : 0))r = mid;
else l = mid;
}
ans = max(ans, t + (i ? b[i - 1] : 0) - (r ? b[r - 1] : 0));
if(r){
ans = max(ans, s - (i - r) - 1);
}
}
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int times = 1;
//cin >> times;
for(int i = 1; i <= times; i++) {
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |