| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 253387 |
2020-07-27T21:05:32 Z |
ChrisT |
Rice Hub (IOI11_ricehub) |
C++17 |
|
31 ms |
2560 KB |
#include<bits/stdc++.h>
#include "ricehub.h"
using namespace std;
int besthub (int r, int l, int *x, long long b) {
vector<long long> psa(r);
auto get = [&] (int pos) {
return pos < 0 ? 0LL : psa[pos];
};
for (int i = 0; i < r; i++) psa[i] = get(i-1) + x[i];
int ret = 0;
for (int i = 0; i < r; i++) { //i^{th} is the median
int low = 1, high = min(r,min(i+1,r-i) * 2), mid, ans = 0;
while (low <= high) {
mid = (low + high) / 2;
int take = (mid - 1) / 2;
long long go = get(i - take - 1) + get(i + take) - get(i) - get(i-1);
if (!(mid & 1)) go += min(i>=take+1?x[i]-x[i-take-1]:INT_MAX,i+take+1<r?x[i+take+1]-x[i]:INT_MAX);
if (go <= b) low = (ans = mid) + 1;
else high = mid - 1;
}
ret = max(ret,ans);
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
256 KB |
Output is correct |
| 5 |
Correct |
0 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
0 ms |
256 KB |
Output is correct |
| 5 |
Correct |
0 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
0 ms |
256 KB |
Output is correct |
| 8 |
Correct |
1 ms |
372 KB |
Output is correct |
| 9 |
Correct |
0 ms |
256 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
256 KB |
Output is correct |
| 12 |
Correct |
0 ms |
256 KB |
Output is correct |
| 13 |
Correct |
1 ms |
256 KB |
Output is correct |
| 14 |
Correct |
0 ms |
256 KB |
Output is correct |
| 15 |
Correct |
0 ms |
256 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
0 ms |
256 KB |
Output is correct |
| 19 |
Correct |
0 ms |
256 KB |
Output is correct |
| 20 |
Correct |
1 ms |
256 KB |
Output is correct |
| 21 |
Correct |
0 ms |
384 KB |
Output is correct |
| 22 |
Correct |
0 ms |
256 KB |
Output is correct |
| 23 |
Correct |
0 ms |
256 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
256 KB |
Output is correct |
| 26 |
Correct |
0 ms |
384 KB |
Output is correct |
| 27 |
Correct |
0 ms |
256 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
256 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
0 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
2 ms |
384 KB |
Output is correct |
| 22 |
Correct |
2 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
2 ms |
384 KB |
Output is correct |
| 25 |
Correct |
2 ms |
384 KB |
Output is correct |
| 26 |
Correct |
2 ms |
384 KB |
Output is correct |
| 27 |
Correct |
2 ms |
384 KB |
Output is correct |
| 28 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
5 ms |
640 KB |
Output is correct |
| 3 |
Correct |
29 ms |
2560 KB |
Output is correct |
| 4 |
Correct |
29 ms |
2560 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1280 KB |
Output is correct |
| 6 |
Correct |
14 ms |
1280 KB |
Output is correct |
| 7 |
Correct |
26 ms |
2304 KB |
Output is correct |
| 8 |
Correct |
27 ms |
2304 KB |
Output is correct |
| 9 |
Correct |
15 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
14 ms |
1280 KB |
Output is correct |
| 11 |
Correct |
31 ms |
2552 KB |
Output is correct |
| 12 |
Correct |
30 ms |
2560 KB |
Output is correct |
| 13 |
Correct |
14 ms |
1280 KB |
Output is correct |
| 14 |
Correct |
14 ms |
1280 KB |
Output is correct |
| 15 |
Correct |
23 ms |
2064 KB |
Output is correct |
| 16 |
Correct |
23 ms |
2048 KB |
Output is correct |
| 17 |
Correct |
27 ms |
2304 KB |
Output is correct |
| 18 |
Correct |
27 ms |
2304 KB |
Output is correct |
| 19 |
Correct |
29 ms |
2432 KB |
Output is correct |
| 20 |
Correct |
29 ms |
2432 KB |
Output is correct |
