#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
template<class T> bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
const ll inf = 1ll << 59;
int n, x[MAX_N];
ll pf[MAX_N];
ll cost(int wid) {
ll res = inf;
for (int i = 1;i + wid - 1 <= n;++i) {
int mid = i + wid / 2;
ll fr = pf[mid-1] - pf[i-1], ba = pf[i+wid-1] - pf[mid];
ll fcnt = mid - i, bcnt = i + wid - 1 - mid;
chmin(res, 1ll * x[mid] * (fcnt - bcnt) - fr + ba);
}
return res;
}
int besthub(int N, int _, int X[], long long B) {
n = N;
for (int i = 0;i < n;++i)
x[i+1] = X[i];
for (int i = 1;i <= n;++i)
pf[i] = pf[i-1] + x[i];
int L = 0, R = N, M;
while (L < R) {
M = L + R >> 1;
if (cost(M+1) <= B)
L = M+1;
else R = M;
}
return L;
}
Compilation message
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:43:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | M = L + R >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
364 KB |
Output is correct |
| 21 |
Correct |
1 ms |
364 KB |
Output is correct |
| 22 |
Correct |
1 ms |
364 KB |
Output is correct |
| 23 |
Correct |
1 ms |
364 KB |
Output is correct |
| 24 |
Correct |
1 ms |
364 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
364 KB |
Output is correct |
| 27 |
Correct |
1 ms |
364 KB |
Output is correct |
| 28 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
364 KB |
Output is correct |
| 21 |
Correct |
1 ms |
492 KB |
Output is correct |
| 22 |
Correct |
1 ms |
492 KB |
Output is correct |
| 23 |
Correct |
1 ms |
492 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
492 KB |
Output is correct |
| 26 |
Correct |
1 ms |
504 KB |
Output is correct |
| 27 |
Correct |
1 ms |
492 KB |
Output is correct |
| 28 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
748 KB |
Output is correct |
| 2 |
Correct |
5 ms |
748 KB |
Output is correct |
| 3 |
Correct |
21 ms |
2924 KB |
Output is correct |
| 4 |
Correct |
19 ms |
2924 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1516 KB |
Output is correct |
| 6 |
Correct |
9 ms |
1516 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2668 KB |
Output is correct |
| 8 |
Correct |
15 ms |
2796 KB |
Output is correct |
| 9 |
Correct |
8 ms |
1516 KB |
Output is correct |
| 10 |
Correct |
10 ms |
1408 KB |
Output is correct |
| 11 |
Correct |
17 ms |
2924 KB |
Output is correct |
| 12 |
Correct |
17 ms |
2924 KB |
Output is correct |
| 13 |
Correct |
9 ms |
1516 KB |
Output is correct |
| 14 |
Correct |
9 ms |
1516 KB |
Output is correct |
| 15 |
Correct |
13 ms |
2284 KB |
Output is correct |
| 16 |
Correct |
13 ms |
2284 KB |
Output is correct |
| 17 |
Correct |
15 ms |
2668 KB |
Output is correct |
| 18 |
Correct |
15 ms |
2688 KB |
Output is correct |
| 19 |
Correct |
16 ms |
2796 KB |
Output is correct |
| 20 |
Correct |
16 ms |
2924 KB |
Output is correct |
