#include<bits/stdc++.h>
#include "ricehub.h"
using namespace std;
int besthub(int n, int L, int X[], long long B){
long long sum = 0,tot = 0;
int num = 0;
int last = 0;
vector<long long> PR(n);
int ans = 0,ps = 0;
for (int i = 0 ; i < n; i++) {
sum += X[i];
tot += X[i];
PR[i] = sum;
num++;
while (true) {
long long e = tot/num;
int pos = lower_bound(X + last, X + i+1, e) - X;
long long D = 0;
long long s = X[pos]*(pos - last + 1) - (PR[pos] - (last ? PR[last-1] : 0)) + (PR[i] - PR[pos]) -X[pos]*( i - pos);
if (s <= B)
if (ans < i - last + 1)
ans = i - last + 1, ps = X[pos];
D = s;
pos = upper_bound(X + last, X + i+1, e) - X - 1;
if (pos <= i && pos >= last) {
s =X[pos]*(pos - last + 1) - (PR[pos] - (last ? PR[last-1] : 0)) + (PR[i] - PR[pos]) -X[pos]*( i - pos);
D = min(D,s);
if (s <= B)
if (ans < i - last + 1)
ans = i - last + 1, ps = X[pos];
}
if (D > B) {
tot-=X[last];
last++;
num--;
continue;
}
else break;
}
}
return ans;
} /*
main() {
int n,L;
long long B;
cin >> n >> L >> B; int X[n];
for (int i = 0; i < n ; i++) cin >> X[i];
cout << besthub(n,L,X,B);
} */
Compilation message
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:9:14: warning: variable 'ps' set but not used [-Wunused-but-set-variable]
int ans = 0,ps = 0;
^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
256 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
256 KB |
Output is correct |
| 9 |
Correct |
5 ms |
256 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
4 ms |
256 KB |
Output is correct |
| 12 |
Correct |
5 ms |
256 KB |
Output is correct |
| 13 |
Correct |
4 ms |
256 KB |
Output is correct |
| 14 |
Correct |
5 ms |
256 KB |
Output is correct |
| 15 |
Correct |
5 ms |
256 KB |
Output is correct |
| 16 |
Correct |
5 ms |
256 KB |
Output is correct |
| 17 |
Correct |
5 ms |
256 KB |
Output is correct |
| 18 |
Correct |
5 ms |
256 KB |
Output is correct |
| 19 |
Correct |
4 ms |
256 KB |
Output is correct |
| 20 |
Correct |
4 ms |
256 KB |
Output is correct |
| 21 |
Correct |
5 ms |
384 KB |
Output is correct |
| 22 |
Correct |
5 ms |
384 KB |
Output is correct |
| 23 |
Correct |
5 ms |
384 KB |
Output is correct |
| 24 |
Correct |
5 ms |
256 KB |
Output is correct |
| 25 |
Correct |
5 ms |
384 KB |
Output is correct |
| 26 |
Correct |
5 ms |
384 KB |
Output is correct |
| 27 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 28 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
256 KB |
Output is correct |
| 6 |
Correct |
5 ms |
256 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
256 KB |
Output is correct |
| 11 |
Correct |
5 ms |
256 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
256 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
256 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
6 ms |
384 KB |
Output is correct |
| 22 |
Correct |
6 ms |
384 KB |
Output is correct |
| 23 |
Correct |
6 ms |
384 KB |
Output is correct |
| 24 |
Correct |
6 ms |
384 KB |
Output is correct |
| 25 |
Correct |
6 ms |
384 KB |
Output is correct |
| 26 |
Correct |
6 ms |
384 KB |
Output is correct |
| 27 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 28 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
512 KB |
Output is correct |
| 2 |
Correct |
9 ms |
512 KB |
Output is correct |
| 3 |
Correct |
26 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
27 ms |
1456 KB |
Output is correct |
| 5 |
Correct |
14 ms |
896 KB |
Output is correct |
| 6 |
Correct |
14 ms |
896 KB |
Output is correct |
| 7 |
Correct |
25 ms |
1536 KB |
Output is correct |
| 8 |
Correct |
25 ms |
1536 KB |
Output is correct |
| 9 |
Correct |
18 ms |
896 KB |
Output is correct |
| 10 |
Correct |
17 ms |
896 KB |
Output is correct |
| 11 |
Correct |
30 ms |
1536 KB |
Output is correct |
| 12 |
Incorrect |
28 ms |
1536 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
