#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=100000, INF=100000000;
///500,000,000
int N;
double a[MAXN], b[MAXN];
bool works(double gain) {
int ap = 0, bp = 0;
double ag = 0, bg = 0;
while (true) {
// Base cases
if (ag >= gain && bg >= gain) return true;
if ( (ag < gain && ap == N) || (bg < gain && bp == N) ) return false;
if (ag < gain) {
ag += a[ap];
ap ++;
bg -= 1;
}
if (bg < gain) {
bg += b[bp];
bp ++;
ag -= 1;
}
}
}
int main () {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
ffi {
cin >> a[i] >> b[i];
a[i] -= 1;
b[i] -= 1;
}
sort(a, a+N, greater<double>());
sort(b, b+N, greater<double>());
double st = 0, en = INF;
while (abs(st - en) > .00005) {
double mid = (st+en)/2;
if (!works(mid)) en = mid;
else st = mid;
}
printf("%.4lf\n", st);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
2 ms |
480 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
2 ms |
480 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
568 KB |
Output is correct |
| 8 |
Correct |
2 ms |
572 KB |
Output is correct |
| 9 |
Correct |
2 ms |
652 KB |
Output is correct |
| 10 |
Correct |
2 ms |
672 KB |
Output is correct |
| 11 |
Correct |
2 ms |
676 KB |
Output is correct |
| 12 |
Correct |
3 ms |
680 KB |
Output is correct |
| 13 |
Correct |
3 ms |
696 KB |
Output is correct |
| 14 |
Correct |
3 ms |
712 KB |
Output is correct |
| 15 |
Correct |
3 ms |
728 KB |
Output is correct |
| 16 |
Correct |
3 ms |
744 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
2 ms |
480 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
568 KB |
Output is correct |
| 8 |
Correct |
2 ms |
572 KB |
Output is correct |
| 9 |
Correct |
2 ms |
652 KB |
Output is correct |
| 10 |
Correct |
2 ms |
672 KB |
Output is correct |
| 11 |
Correct |
2 ms |
676 KB |
Output is correct |
| 12 |
Correct |
3 ms |
680 KB |
Output is correct |
| 13 |
Correct |
3 ms |
696 KB |
Output is correct |
| 14 |
Correct |
3 ms |
712 KB |
Output is correct |
| 15 |
Correct |
3 ms |
728 KB |
Output is correct |
| 16 |
Correct |
3 ms |
744 KB |
Output is correct |
| 17 |
Correct |
112 ms |
3712 KB |
Output is correct |
| 18 |
Correct |
121 ms |
4124 KB |
Output is correct |
| 19 |
Correct |
116 ms |
4180 KB |
Output is correct |
| 20 |
Correct |
118 ms |
4180 KB |
Output is correct |
| 21 |
Correct |
128 ms |
4184 KB |
Output is correct |
| 22 |
Correct |
111 ms |
4304 KB |
Output is correct |
| 23 |
Correct |
116 ms |
4304 KB |
Output is correct |
| 24 |
Correct |
114 ms |
4304 KB |
Output is correct |
| 25 |
Correct |
112 ms |
4304 KB |
Output is correct |
| 26 |
Correct |
123 ms |
4304 KB |
Output is correct |
