#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
typedef long long ll;
ll num[MAXN], soma[MAXN], b;
int n;
bool ok(int k)
{
if (k == 1) return true;
ll c = soma[k]-soma[1]-(k-1)*num[1];
int ind = 1;
for (int i = 2; i <= k; i++)
{
ll aux = (i-1)*num[i]-soma[i-1]+soma[k]-soma[i]-(k-i)*num[i];
if (aux <= c) c = aux, ind = i;
}
if (c <= b) return true;
for (int i = k+1; i <= n; i++)
{
c -= (num[ind]-num[i-k]);
c += (num[i]-num[ind]);
int j = ind+1;
ll aux = (j-(i-k+1))*num[j]-(soma[j-1]-soma[i-k]) + (soma[i]-soma[j])-(i-j)*num[j];
if (aux <= c)
{
c = aux;
ind = j;
}
if (c <= b) return true;
}
return false;
}
int busca(void)
{
int ini = 1, fim = n;
while (ini <= fim)
{
int mid = (ini+fim)>>1;
if (mid == n && ok(mid)) return n;
else if (mid == n)
{
fim = mid-1;
continue;
}
if (ok(mid) && !ok(mid+1)) return mid;
else if (ok(mid) && ok(mid+1)) ini = mid+1;
else if (!ok(mid)) fim = mid-1;
}
}
int besthub(int r, int l, int x[], ll k)
{
n = r, b = k;
for (int i = 1; i <= n; i++)
{
num[i] = x[i-1];
soma[i] = soma[i-1]+num[i];
}
return busca();
}
Compilation message
ricehub.cpp: In function 'int busca()':
ricehub.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
496 KB |
Output is correct |
| 3 |
Correct |
2 ms |
496 KB |
Output is correct |
| 4 |
Correct |
2 ms |
496 KB |
Output is correct |
| 5 |
Correct |
2 ms |
496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
496 KB |
Output is correct |
| 2 |
Correct |
2 ms |
496 KB |
Output is correct |
| 3 |
Correct |
2 ms |
496 KB |
Output is correct |
| 4 |
Correct |
2 ms |
496 KB |
Output is correct |
| 5 |
Correct |
2 ms |
676 KB |
Output is correct |
| 6 |
Correct |
2 ms |
676 KB |
Output is correct |
| 7 |
Correct |
2 ms |
680 KB |
Output is correct |
| 8 |
Correct |
2 ms |
680 KB |
Output is correct |
| 9 |
Correct |
2 ms |
680 KB |
Output is correct |
| 10 |
Correct |
2 ms |
688 KB |
Output is correct |
| 11 |
Correct |
2 ms |
688 KB |
Output is correct |
| 12 |
Correct |
3 ms |
688 KB |
Output is correct |
| 13 |
Correct |
2 ms |
688 KB |
Output is correct |
| 14 |
Correct |
2 ms |
688 KB |
Output is correct |
| 15 |
Correct |
3 ms |
688 KB |
Output is correct |
| 16 |
Correct |
2 ms |
688 KB |
Output is correct |
| 17 |
Correct |
2 ms |
688 KB |
Output is correct |
| 18 |
Correct |
2 ms |
688 KB |
Output is correct |
| 19 |
Correct |
2 ms |
688 KB |
Output is correct |
| 20 |
Correct |
2 ms |
688 KB |
Output is correct |
| 21 |
Correct |
2 ms |
688 KB |
Output is correct |
| 22 |
Correct |
2 ms |
688 KB |
Output is correct |
| 23 |
Correct |
2 ms |
688 KB |
Output is correct |
| 24 |
Correct |
2 ms |
724 KB |
Output is correct |
| 25 |
Correct |
2 ms |
724 KB |
Output is correct |
| 26 |
Correct |
2 ms |
724 KB |
Output is correct |
| 27 |
Correct |
2 ms |
792 KB |
Output is correct |
| 28 |
Correct |
2 ms |
924 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
924 KB |
Output is correct |
| 2 |
Correct |
2 ms |
924 KB |
Output is correct |
| 3 |
Correct |
2 ms |
924 KB |
Output is correct |
| 4 |
Correct |
3 ms |
924 KB |
Output is correct |
| 5 |
Correct |
3 ms |
924 KB |
Output is correct |
| 6 |
Correct |
2 ms |
924 KB |
Output is correct |
| 7 |
Correct |
3 ms |
924 KB |
Output is correct |
| 8 |
Correct |
2 ms |
964 KB |
Output is correct |
| 9 |
Correct |
3 ms |
964 KB |
Output is correct |
| 10 |
Correct |
2 ms |
964 KB |
Output is correct |
| 11 |
Correct |
2 ms |
964 KB |
Output is correct |
| 12 |
Correct |
3 ms |
964 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1052 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1076 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1076 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1076 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1076 KB |
Output is correct |
| 18 |
Correct |
2 ms |
1076 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1192 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1192 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1224 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1244 KB |
Output is correct |
| 23 |
Correct |
3 ms |
1332 KB |
Output is correct |
| 24 |
Correct |
3 ms |
1332 KB |
Output is correct |
| 25 |
Correct |
4 ms |
1336 KB |
Output is correct |
| 26 |
Correct |
4 ms |
1376 KB |
Output is correct |
| 27 |
Correct |
3 ms |
1416 KB |
Output is correct |
| 28 |
Correct |
3 ms |
1456 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
1880 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2020 KB |
Output is correct |
| 3 |
Correct |
29 ms |
4584 KB |
Output is correct |
| 4 |
Correct |
28 ms |
5648 KB |
Output is correct |
| 5 |
Correct |
11 ms |
5648 KB |
Output is correct |
| 6 |
Correct |
12 ms |
5648 KB |
Output is correct |
| 7 |
Correct |
28 ms |
7136 KB |
Output is correct |
| 8 |
Correct |
28 ms |
7908 KB |
Output is correct |
| 9 |
Correct |
11 ms |
7908 KB |
Output is correct |
| 10 |
Correct |
11 ms |
7908 KB |
Output is correct |
| 11 |
Correct |
32 ms |
9536 KB |
Output is correct |
| 12 |
Correct |
34 ms |
10596 KB |
Output is correct |
| 13 |
Correct |
12 ms |
10596 KB |
Output is correct |
| 14 |
Correct |
11 ms |
10596 KB |
Output is correct |
| 15 |
Correct |
24 ms |
11668 KB |
Output is correct |
| 16 |
Correct |
23 ms |
12456 KB |
Output is correct |
| 17 |
Correct |
28 ms |
13756 KB |
Output is correct |
| 18 |
Correct |
29 ms |
14696 KB |
Output is correct |
| 19 |
Correct |
36 ms |
15772 KB |
Output is correct |
| 20 |
Correct |
34 ms |
16724 KB |
Output is correct |
