#include "bits/stdc++.h"
#include "ricehub.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
vi prefix, suffix;
vi rice;
ll MAX;
ll cost(ll l, ll r){
ll m = (l+r)/2;
ll c = prefix[r] - prefix[m] - rice[m] * (r-m);
c += suffix[l] - suffix[m] - (MAX - rice[m]) * (m-l);
return c;
}
bool possible(int l, int r, ll B){
//cout <<l << " " << r << " " << cost(l,r) << endl;
return cost(l, r) <= B;
}
int besthub(int R, int L, int X[], ll B)
{
MAX = L;
rice.resize(R);
for(int i = 0; i < R; i++) rice[i] = X[i];
prefix.assign(R+1, 0); suffix.assign(R+1, 0);
for(int i = 1; i <= R; i++) prefix[i] = prefix[i-1] + rice[i-1];
for(int i = R-1; i >= 0; i--) suffix[i] = suffix[i+1] + L - rice[i];
ll l = 0, r = 0;
ll best = -1;
while(!(l == R and r == R)){
while(possible(l, r, B)){
best = max(best, r-l);
if(r < R) r++;
else break;
}
l++;
}
return best;
}
/*
int test[] = {1, 2, 10, 12, 14};
int main(){
cout << besthub(5, 20, test, 6)<<endl;
}
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
392 KB |
Output is correct |
| 3 |
Correct |
2 ms |
572 KB |
Output is correct |
| 4 |
Correct |
2 ms |
572 KB |
Output is correct |
| 5 |
Correct |
2 ms |
572 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
572 KB |
Output is correct |
| 2 |
Correct |
2 ms |
572 KB |
Output is correct |
| 3 |
Correct |
2 ms |
572 KB |
Output is correct |
| 4 |
Correct |
2 ms |
572 KB |
Output is correct |
| 5 |
Correct |
3 ms |
572 KB |
Output is correct |
| 6 |
Correct |
2 ms |
572 KB |
Output is correct |
| 7 |
Correct |
2 ms |
608 KB |
Output is correct |
| 8 |
Correct |
3 ms |
608 KB |
Output is correct |
| 9 |
Correct |
2 ms |
608 KB |
Output is correct |
| 10 |
Correct |
2 ms |
608 KB |
Output is correct |
| 11 |
Correct |
2 ms |
612 KB |
Output is correct |
| 12 |
Correct |
2 ms |
620 KB |
Output is correct |
| 13 |
Correct |
2 ms |
620 KB |
Output is correct |
| 14 |
Correct |
3 ms |
620 KB |
Output is correct |
| 15 |
Correct |
2 ms |
620 KB |
Output is correct |
| 16 |
Correct |
3 ms |
620 KB |
Output is correct |
| 17 |
Correct |
2 ms |
620 KB |
Output is correct |
| 18 |
Correct |
2 ms |
620 KB |
Output is correct |
| 19 |
Correct |
3 ms |
620 KB |
Output is correct |
| 20 |
Correct |
2 ms |
620 KB |
Output is correct |
| 21 |
Correct |
3 ms |
620 KB |
Output is correct |
| 22 |
Correct |
2 ms |
620 KB |
Output is correct |
| 23 |
Correct |
2 ms |
620 KB |
Output is correct |
| 24 |
Correct |
2 ms |
620 KB |
Output is correct |
| 25 |
Correct |
2 ms |
620 KB |
Output is correct |
| 26 |
Correct |
3 ms |
620 KB |
Output is correct |
| 27 |
Correct |
2 ms |
620 KB |
Output is correct |
| 28 |
Correct |
2 ms |
620 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
620 KB |
Output is correct |
| 2 |
Correct |
3 ms |
620 KB |
Output is correct |
| 3 |
Correct |
2 ms |
620 KB |
Output is correct |
| 4 |
Correct |
2 ms |
620 KB |
Output is correct |
| 5 |
Correct |
2 ms |
620 KB |
Output is correct |
| 6 |
Correct |
2 ms |
620 KB |
Output is correct |
| 7 |
Correct |
2 ms |
620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
620 KB |
Output is correct |
| 9 |
Correct |
2 ms |
624 KB |
Output is correct |
| 10 |
Correct |
2 ms |
624 KB |
Output is correct |
| 11 |
Correct |
3 ms |
624 KB |
Output is correct |
| 12 |
Correct |
2 ms |
624 KB |
Output is correct |
| 13 |
Correct |
2 ms |
624 KB |
Output is correct |
| 14 |
Correct |
2 ms |
624 KB |
Output is correct |
| 15 |
Correct |
2 ms |
748 KB |
Output is correct |
| 16 |
Correct |
2 ms |
748 KB |
Output is correct |
| 17 |
Correct |
3 ms |
748 KB |
Output is correct |
| 18 |
Correct |
3 ms |
748 KB |
Output is correct |
| 19 |
Correct |
2 ms |
748 KB |
Output is correct |
| 20 |
Correct |
2 ms |
748 KB |
Output is correct |
| 21 |
Correct |
3 ms |
748 KB |
Output is correct |
| 22 |
Correct |
3 ms |
764 KB |
Output is correct |
| 23 |
Correct |
3 ms |
764 KB |
Output is correct |
| 24 |
Correct |
5 ms |
764 KB |
Output is correct |
| 25 |
Correct |
3 ms |
764 KB |
Output is correct |
| 26 |
Correct |
3 ms |
764 KB |
Output is correct |
| 27 |
Correct |
2 ms |
764 KB |
Output is correct |
| 28 |
Correct |
3 ms |
764 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
1148 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1148 KB |
Output is correct |
| 3 |
Correct |
42 ms |
3324 KB |
Output is correct |
| 4 |
Correct |
68 ms |
3324 KB |
Output is correct |
| 5 |
Correct |
9 ms |
3324 KB |
Output is correct |
| 6 |
Correct |
19 ms |
3324 KB |
Output is correct |
| 7 |
Correct |
19 ms |
3324 KB |
Output is correct |
| 8 |
Correct |
34 ms |
3324 KB |
Output is correct |
| 9 |
Correct |
12 ms |
3324 KB |
Output is correct |
| 10 |
Correct |
10 ms |
3324 KB |
Output is correct |
| 11 |
Correct |
28 ms |
3452 KB |
Output is correct |
| 12 |
Correct |
24 ms |
3452 KB |
Output is correct |
| 13 |
Correct |
11 ms |
3452 KB |
Output is correct |
| 14 |
Correct |
12 ms |
3452 KB |
Output is correct |
| 15 |
Correct |
31 ms |
3452 KB |
Output is correct |
| 16 |
Correct |
24 ms |
3452 KB |
Output is correct |
| 17 |
Correct |
23 ms |
3452 KB |
Output is correct |
| 18 |
Correct |
35 ms |
3452 KB |
Output is correct |
| 19 |
Correct |
27 ms |
3452 KB |
Output is correct |
| 20 |
Correct |
26 ms |
3452 KB |
Output is correct |
