| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 65714 |
2018-08-08T13:11:48 Z |
polyfish |
Sure Bet (CEOI17_sure) |
C++14 |
|
179 ms |
9652 KB |
//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int MAX_N = 100002;
int n;
double A[MAX_N], B[MAX_N];
void enter() {
cin >> n;
for (int i=1; i<=n; ++i) {
cin >> A[i] >> B[i];
}
sort(A+1, A+n+1);
sort(B+1, B+n+1);
reverse(A+1, A+n+1);
reverse(B+1, B+n+1);
for (int i=1; i<=n; ++i) {
A[i] += A[i-1];
B[i] += B[i-1];
}
}
double bisect(int v) {
int l = 0, r = min(v, n);
while (r-l+1>=3) {
int mid1 = l + (r - l + 1) / 3;
int mid2 = r - (r - l + 1) / 3;
if (min(A[mid1], B[v-mid1]) > min(A[mid2], B[v-mid2]))
r = mid2;
else
l = mid1;
}
double res = 0;
for (int i=l; i<=r; ++i)
res = max(res, min(A[i], B[v-i]));
return res;
}
void solve() {
double res = 0;
//PR(A, n);
//PR(B, n);
//debug(bisect(5) - 5);
for (int i=1; i<=2*n; ++i)
res = max(res, bisect(i) - i);
cout << setiosflags(ios::fixed) << setprecision(4) << res;
}
int main() {
//#define OFFLINE_JUDGE doraemon
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
enter();
solve();
}
| # |
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 |
412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
416 KB |
Output is correct |
| 5 |
Correct |
2 ms |
636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
636 KB |
Output is correct |
| # |
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 |
412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
416 KB |
Output is correct |
| 5 |
Correct |
2 ms |
636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
636 KB |
Output is correct |
| 8 |
Correct |
2 ms |
636 KB |
Output is correct |
| 9 |
Correct |
2 ms |
636 KB |
Output is correct |
| 10 |
Correct |
2 ms |
636 KB |
Output is correct |
| 11 |
Correct |
2 ms |
696 KB |
Output is correct |
| 12 |
Correct |
3 ms |
700 KB |
Output is correct |
| 13 |
Correct |
4 ms |
716 KB |
Output is correct |
| 14 |
Correct |
4 ms |
748 KB |
Output is correct |
| 15 |
Correct |
4 ms |
780 KB |
Output is correct |
| 16 |
Correct |
4 ms |
796 KB |
Output is correct |
| # |
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 |
412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
416 KB |
Output is correct |
| 5 |
Correct |
2 ms |
636 KB |
Output is correct |
| 6 |
Correct |
2 ms |
636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
636 KB |
Output is correct |
| 8 |
Correct |
2 ms |
636 KB |
Output is correct |
| 9 |
Correct |
2 ms |
636 KB |
Output is correct |
| 10 |
Correct |
2 ms |
636 KB |
Output is correct |
| 11 |
Correct |
2 ms |
696 KB |
Output is correct |
| 12 |
Correct |
3 ms |
700 KB |
Output is correct |
| 13 |
Correct |
4 ms |
716 KB |
Output is correct |
| 14 |
Correct |
4 ms |
748 KB |
Output is correct |
| 15 |
Correct |
4 ms |
780 KB |
Output is correct |
| 16 |
Correct |
4 ms |
796 KB |
Output is correct |
| 17 |
Correct |
175 ms |
3792 KB |
Output is correct |
| 18 |
Correct |
175 ms |
5272 KB |
Output is correct |
| 19 |
Correct |
174 ms |
6524 KB |
Output is correct |
| 20 |
Correct |
177 ms |
7864 KB |
Output is correct |
| 21 |
Incorrect |
179 ms |
9652 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
