| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1006676 |
2024-06-24T07:00:01 Z |
uma |
Rice Hub (IOI11_ricehub) |
C++14 |
|
11 ms |
4452 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
