// C++ Template
#include "bits/stdc++.h"
using namespace std;
// Type
typedef long long ll;
typedef long double ld;
// Pair/Vector
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
// Priority Queue
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
// Macro
#define stat(x) (x) && cout << "YES\n" || cout << "NO\n";
#ifdef LOCAL
#define debug(x) cout << #x << " = " << x << "\n";
#else
#define debug(x) ;
#endif
// Custom output
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x){
out << "(" << x.first << ", " << x.second << ")";
return out;
}
template <class T>
ostream& operator << (ostream& out, vector<T> x){
out << "[";
for (int i=0; i<x.size(); i++){
if (i) out << ", ";
out << x[i];
}
out << "]";
return out;
}
void fastio(string finp = "", string fout = ""){
if (fopen(finp.c_str(), "r")){
freopen(finp.c_str(), "r", stdin);
freopen(fout.c_str(), "w", stdout);
}
}
// Const
const int interactive = 0;
const ld PI = acos(-1.0);
const ll allmod[2] = {int(1e9)+7, 998244353};
const ll mod = allmod[0];
const ll maxn = 2e5;
const ll inf = 1e18;
const int multitest = 0;
#define mid ((l+r)/2)
#define int long long
vector<ld> a, b, val;
int n;
ld sm = 0.0;
int it = 0;
pair<ld, ld> get(int x){
if (x > n) return {(ld)-inf, (ld)inf};
else return {sm-x, val[x]};
}
void main_program(){
cin >> n;
a.assign(n+1, 0.0);
b.assign(n+1, 0.0);
val.assign(n+1, 0.0);
for (int i=1; i<=n; i++) cin >> a[i] >> b[i];
sort(a.begin()+1, a.end(), greater<ld>());
sort(b.begin()+1, b.end(), greater<ld>());
for (int i=1; i<=n; i++) val[i] = val[i-1] + b[i] - 1;
debug(a); debug(b); debug(val);
ld res = 0.0;
for (int cnt = 0; cnt <= n; cnt++){
sm += a[cnt];
int l = 0, r = n;
while (l < r){
debug(l); debug(r); debug(cnt);
it++; if (it >= 200) return;
ld vala, valb;
tie(vala, valb) = get(mid);
debug(vala); debug(valb);
if (vala < valb) r = mid;
else l = mid+1;
}
debug(l); debug(r); debug(cnt);
res = max(res, max(get(l-1).second, get(l).first) - cnt);
}
// cout << fixed << setprecision(4) << res;
printf("%.4lf",(double)res);
}
void pre_main(){
}
signed main(){
#ifdef LOCAL
auto start_time = chrono::high_resolution_clock::now();
#endif
if (!interactive) {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
#ifndef ONLINE_JUDGE
fastio(".inp", ".out");
#endif
int t = 1;
if (multitest) cin >> t;
pre_main();
while (t--) main_program();
#ifdef LOCAL
auto end_time = chrono::high_resolution_clock::now();
double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
cout << "\n[" << duration << "ms]\n";
#endif
}
Compilation message
sure.cpp: In function 'void fastio(std::string, std::string)':
sure.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | freopen(finp.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sure.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | freopen(fout.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
