#include<bits/stdc++.h>
#include <ricehub.h>
#define pii pair<int,int>
#define f first
#define ll long long
#define s second
#define pb push_back
using namespace std ;
const int maxn = 1e5 + 5 ;
ll n, mx, p[maxn], num[maxn], qtd, indbest ;
bool ok(int k){
if(k == 1) return true ;
// cout << "com k = " << k << ":\n" ;
ll c = p[k] - p[1] -((k-1)*num[1]) ;
indbest = 1 ;
for(int i = 2 ; i <= k ; i++){
ll ans = p[k] - p[i] - ((k-i)*num[i]) + ((i - 1)*num[i]) - p[i-1] ;
if(ans <= c) c = ans, indbest = i ;
// cout << i << " " << k-i << " " << ans << "\n" ;
}
if(c <= mx) return true ;
for(int i = k+1 ; i <= qtd ; i++){
c -= (num[indbest] - num[i-k]), c += (num[i] - num[indbest]) ;
int j = indbest + 1 ;
ll ans = (j-(i-k+1))*num[j] - p[j-1] + p[i-k] + p[i] - p[j] - (i-j)*num[j] ;
if(ans <= c) c = ans, indbest = j ;
// cout << i << " " << j << " " << ans << "\n" ;
if(c <= mx) return true ;
}
return false ;
}
int bb(){
int ini = 1, fim = qtd ;
int best = 1, mid ;
while(ini <= fim){
mid = (ini + fim)/2 ;
if(ok(mid)){
best = mid ;
ini = mid + 1 ;
}
else fim = mid - 1 ;
}
return best ;
}
int besthub(int R, int L, int x[maxn], ll B){
mx = B, qtd = R ;
for(int i = 1 ; i <= R ; i++){
num[i] = x[i-1] ;
p[i] = p[i-1] + num[i] ;
}
return bb() ;
// cout << bb() << "\n" ;
}
/*int main(){
int m[5] = {1, 2, 10, 12, 14} ;
besthub(5, 20, m, 6) ;
}*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
204 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
204 KB |
Output is correct |
| 27 |
Correct |
1 ms |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
2 ms |
332 KB |
Output is correct |
| 25 |
Correct |
2 ms |
332 KB |
Output is correct |
| 26 |
Correct |
2 ms |
332 KB |
Output is correct |
| 27 |
Correct |
2 ms |
440 KB |
Output is correct |
| 28 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
588 KB |
Output is correct |
| 2 |
Correct |
4 ms |
588 KB |
Output is correct |
| 3 |
Correct |
18 ms |
2256 KB |
Output is correct |
| 4 |
Correct |
18 ms |
2232 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1612 KB |
Output is correct |
| 6 |
Correct |
10 ms |
1592 KB |
Output is correct |
| 7 |
Correct |
17 ms |
3056 KB |
Output is correct |
| 8 |
Correct |
17 ms |
3000 KB |
Output is correct |
| 9 |
Correct |
8 ms |
1484 KB |
Output is correct |
| 10 |
Correct |
8 ms |
1464 KB |
Output is correct |
| 11 |
Correct |
20 ms |
3212 KB |
Output is correct |
| 12 |
Correct |
18 ms |
3268 KB |
Output is correct |
| 13 |
Correct |
9 ms |
1612 KB |
Output is correct |
| 14 |
Correct |
9 ms |
1612 KB |
Output is correct |
| 15 |
Correct |
15 ms |
2508 KB |
Output is correct |
| 16 |
Correct |
14 ms |
2508 KB |
Output is correct |
| 17 |
Correct |
17 ms |
2952 KB |
Output is correct |
| 18 |
Correct |
17 ms |
2924 KB |
Output is correct |
| 19 |
Correct |
18 ms |
3276 KB |
Output is correct |
| 20 |
Correct |
18 ms |
3116 KB |
Output is correct |
