#include "ricehub.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int besthub(int R, int L, int positions[], long long B){
int n = R;
//sort(positions.begin(), positions.end());
vector<ll> prefixSum(n, 0);
prefixSum[0] = positions[0];
for (int i = 1; i < n; ++i) {
prefixSum[i] = prefixSum[i - 1] + positions[i];
}
int maxRiceBags = 0;
int left = 0;
for (int right = 0; right < n; ++right) {
int median = left + (right - left) / 2;
// Calculate the left part cost
ll leftSum = median > 0 ? prefixSum[median - 1] - (left > 0 ? prefixSum[left - 1] : 0) : 0;
ll leftCost = (ll)(median - left) * positions[median] - leftSum;
// Calculate the right part cost
ll rightSum = prefixSum[right] - prefixSum[median];
ll rightCost = rightSum - (ll)(right - median) * positions[median];
ll currentCost = leftCost + rightCost;
while (currentCost > B && left <= median) {
left++;
median = left + (right - left) / 2;
// Recalculate the left part cost
leftSum = median > 0 ? prefixSum[median - 1] - (left > 0 ? prefixSum[left - 1] : 0) : 0;
leftCost = (ll)(median - left) * positions[median] - leftSum;
// Recalculate the right part cost
rightSum = prefixSum[right] - prefixSum[median];
rightCost = rightSum - (ll)(right - median) * positions[median];
currentCost = leftCost + rightCost;
}
maxRiceBags = max(maxRiceBags, right - left + 1);
}
return maxRiceBags;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
444 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
604 KB |
Output is correct |
26 |
Correct |
0 ms |
452 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
452 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
448 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
9 ms |
4452 KB |
Output is correct |
4 |
Correct |
11 ms |
4444 KB |
Output is correct |
5 |
Correct |
7 ms |
3164 KB |
Output is correct |
6 |
Correct |
4 ms |
3252 KB |
Output is correct |
7 |
Correct |
8 ms |
4188 KB |
Output is correct |
8 |
Correct |
8 ms |
4200 KB |
Output is correct |
9 |
Correct |
4 ms |
3164 KB |
Output is correct |
10 |
Correct |
4 ms |
3164 KB |
Output is correct |
11 |
Correct |
9 ms |
4424 KB |
Output is correct |
12 |
Correct |
9 ms |
4444 KB |
Output is correct |
13 |
Correct |
4 ms |
3420 KB |
Output is correct |
14 |
Correct |
4 ms |
3420 KB |
Output is correct |
15 |
Correct |
7 ms |
3892 KB |
Output is correct |
16 |
Correct |
7 ms |
4032 KB |
Output is correct |
17 |
Correct |
8 ms |
4188 KB |
Output is correct |
18 |
Correct |
8 ms |
4188 KB |
Output is correct |
19 |
Correct |
8 ms |
4188 KB |
Output is correct |
20 |
Correct |
8 ms |
4184 KB |
Output is correct |