Submission #1006676

#TimeUsernameProblemLanguageResultExecution timeMemory
1006676umaRice Hub (IOI11_ricehub)C++14
100 / 100
11 ms4452 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...