#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
const int N = 1e5 + 5;
int n;
int a[N];
ll m;
ll L[N];
int ptr, ans = 1;
ll getL(int i, int j) {
return (ll) (j - i + 1) * a[j] - (L[j] - L[i - 1]);
}
ll getR(int i, int j) {
return L[j] - L[i - 1] - (ll) (j - i + 1) * a[i];
}
bool check(int i, int j) {
ll need = getL(i, j);
if(need > m)
return 0;
ans = max(ans, j - i + 1);
ptr = max(ptr, j);
if(getL(i, j) + getR(j, ptr) <= m)
ans = max(ans, ptr - i + 1);
while(ptr + 1 <= n and a[ptr + 1] - a[j] <= a[j] - a[i]) {
ptr++;
if(getL(i, j) + getR(j, ptr) <= m)
ans = max(ans, ptr - i + 1);
else {
ptr--;
return 0;
}
}
return 1;
}
void solve() {
for(int i = 1; i <= n; i++)
L[i] = L[i - 1] + a[i];
:: ptr = 1;
int ptr = 1;
for(int i = 1; i <= n; i++) {
ptr = max(ptr, i);
while(ptr + 1 <= n and check(i, ptr + 1))
ptr++;
}
}
int besthub(int R, int L, int X[], long long B) {
n = R;
m = B;
for(int i = 0; i < n; i++) {
a[i + 1] = X[i];
}
for(int i = 1; i <= n; i++) {
a[i] = L - X[n - i] + 1;
}
solve();
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
6800 KB |
Output is correct |
2 |
Correct |
0 ms |
6800 KB |
Output is correct |
3 |
Correct |
0 ms |
6800 KB |
Output is correct |
4 |
Correct |
0 ms |
6800 KB |
Output is correct |
5 |
Correct |
0 ms |
6800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
6800 KB |
Output is correct |
2 |
Correct |
0 ms |
6800 KB |
Output is correct |
3 |
Correct |
0 ms |
6800 KB |
Output is correct |
4 |
Correct |
0 ms |
6800 KB |
Output is correct |
5 |
Correct |
0 ms |
6800 KB |
Output is correct |
6 |
Correct |
0 ms |
6800 KB |
Output is correct |
7 |
Correct |
0 ms |
6800 KB |
Output is correct |
8 |
Correct |
0 ms |
6800 KB |
Output is correct |
9 |
Correct |
0 ms |
6800 KB |
Output is correct |
10 |
Correct |
0 ms |
6800 KB |
Output is correct |
11 |
Correct |
0 ms |
6800 KB |
Output is correct |
12 |
Correct |
0 ms |
6800 KB |
Output is correct |
13 |
Correct |
0 ms |
6800 KB |
Output is correct |
14 |
Correct |
0 ms |
6800 KB |
Output is correct |
15 |
Correct |
0 ms |
6800 KB |
Output is correct |
16 |
Correct |
0 ms |
6800 KB |
Output is correct |
17 |
Correct |
0 ms |
6800 KB |
Output is correct |
18 |
Correct |
0 ms |
6800 KB |
Output is correct |
19 |
Correct |
0 ms |
6800 KB |
Output is correct |
20 |
Correct |
0 ms |
6800 KB |
Output is correct |
21 |
Correct |
0 ms |
6800 KB |
Output is correct |
22 |
Correct |
0 ms |
6800 KB |
Output is correct |
23 |
Correct |
0 ms |
6800 KB |
Output is correct |
24 |
Correct |
0 ms |
6800 KB |
Output is correct |
25 |
Correct |
0 ms |
6800 KB |
Output is correct |
26 |
Correct |
0 ms |
6800 KB |
Output is correct |
27 |
Incorrect |
0 ms |
6800 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
6800 KB |
Output is correct |
2 |
Correct |
0 ms |
6800 KB |
Output is correct |
3 |
Correct |
0 ms |
6800 KB |
Output is correct |
4 |
Correct |
0 ms |
6800 KB |
Output is correct |
5 |
Correct |
0 ms |
6800 KB |
Output is correct |
6 |
Correct |
0 ms |
6800 KB |
Output is correct |
7 |
Correct |
0 ms |
6800 KB |
Output is correct |
8 |
Correct |
0 ms |
6800 KB |
Output is correct |
9 |
Correct |
0 ms |
6800 KB |
Output is correct |
10 |
Correct |
0 ms |
6800 KB |
Output is correct |
11 |
Correct |
0 ms |
6800 KB |
Output is correct |
12 |
Correct |
0 ms |
6800 KB |
Output is correct |
13 |
Correct |
0 ms |
6800 KB |
Output is correct |
14 |
Correct |
0 ms |
6800 KB |
Output is correct |
15 |
Correct |
0 ms |
6800 KB |
Output is correct |
16 |
Correct |
0 ms |
6800 KB |
Output is correct |
17 |
Correct |
0 ms |
6800 KB |
Output is correct |
18 |
Incorrect |
0 ms |
6800 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
6800 KB |
Output is correct |
2 |
Correct |
5 ms |
6800 KB |
Output is correct |
3 |
Correct |
23 ms |
6800 KB |
Output is correct |
4 |
Correct |
17 ms |
6800 KB |
Output is correct |
5 |
Correct |
8 ms |
6800 KB |
Output is correct |
6 |
Correct |
11 ms |
6800 KB |
Output is correct |
7 |
Correct |
22 ms |
6800 KB |
Output is correct |
8 |
Correct |
19 ms |
6800 KB |
Output is correct |
9 |
Correct |
0 ms |
6800 KB |
Output is correct |
10 |
Correct |
7 ms |
6800 KB |
Output is correct |
11 |
Correct |
19 ms |
6800 KB |
Output is correct |
12 |
Correct |
23 ms |
6800 KB |
Output is correct |
13 |
Correct |
11 ms |
6800 KB |
Output is correct |
14 |
Correct |
12 ms |
6800 KB |
Output is correct |
15 |
Correct |
16 ms |
6800 KB |
Output is correct |
16 |
Incorrect |
11 ms |
6800 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |