#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
long long budget_handler;
long long ricefield_count;
long long len;
long long arr[100001];
long long pf[100001];
void pfcompute() {
pf[0] = arr[0];
for (long long i=1; i<ricefield_count; i++) {
pf[i] = arr[i] + pf[i-1];
}
}
long long pfq(long long a, long long b) {
if (a == 0) return pf[b];
return pf[b] - pf[a-1];
}
long long summed_range(long long left, long long right) {
//
long long median = (left+right)/2;
long long medscore = arr[median];
long long sm = 0;
// from left to median
long long countl = median - left;
long long suml = pfq(left, median-1);
sm += (countl * medscore) - suml;
// from median to right
long long countr = right - median + 1;
long long sumr = pfq(median, right);
sm += sumr - (countr * medscore);
return sm;
}
long long furthest_valid(long long leftlock) {
long long low = leftlock;
long long high = ricefield_count;
long long mid;
while (low + 1 < high) {
mid = (low + high) / 2;
if (summed_range(leftlock, mid) <= budget_handler) {
low = mid;
}
else {
high = mid;
}
}
if (high != ricefield_count) {
if (summed_range(leftlock, high) <= budget_handler) {
return high;
}
}
return low;
}
int besthub(int R, int L, int X[], long long B) {
budget_handler = B;
len = L;
ricefield_count = R;
for (long long i=0; i<R; i++) {
arr[i] = X[i];
}
pfcompute();
long long mx = 0;
for (long long i=0; i<R; i++) {
long long besthere = furthest_valid(i);
// cout << i << " : " << besthere << endl;
mx = max(mx, besthere-i+1);
}
return mx;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
380 KB |
Output is correct |
18 |
Correct |
10 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
2 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
304 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
384 KB |
Output is correct |
23 |
Correct |
3 ms |
512 KB |
Output is correct |
24 |
Correct |
3 ms |
640 KB |
Output is correct |
25 |
Correct |
3 ms |
512 KB |
Output is correct |
26 |
Correct |
3 ms |
512 KB |
Output is correct |
27 |
Correct |
3 ms |
376 KB |
Output is correct |
28 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
768 KB |
Output is correct |
2 |
Correct |
6 ms |
768 KB |
Output is correct |
3 |
Correct |
23 ms |
2288 KB |
Output is correct |
4 |
Correct |
23 ms |
3328 KB |
Output is correct |
5 |
Correct |
11 ms |
1664 KB |
Output is correct |
6 |
Correct |
12 ms |
1664 KB |
Output is correct |
7 |
Correct |
21 ms |
3072 KB |
Output is correct |
8 |
Correct |
21 ms |
3064 KB |
Output is correct |
9 |
Correct |
12 ms |
1664 KB |
Output is correct |
10 |
Correct |
11 ms |
1664 KB |
Output is correct |
11 |
Correct |
25 ms |
3328 KB |
Output is correct |
12 |
Correct |
26 ms |
3328 KB |
Output is correct |
13 |
Correct |
13 ms |
1792 KB |
Output is correct |
14 |
Correct |
16 ms |
1792 KB |
Output is correct |
15 |
Correct |
20 ms |
2560 KB |
Output is correct |
16 |
Correct |
20 ms |
2636 KB |
Output is correct |
17 |
Correct |
23 ms |
3072 KB |
Output is correct |
18 |
Correct |
22 ms |
3072 KB |
Output is correct |
19 |
Correct |
23 ms |
3200 KB |
Output is correct |
20 |
Correct |
23 ms |
3192 KB |
Output is correct |