Submission #1006713

#TimeUsernameProblemLanguageResultExecution timeMemory
1006713umaRice Hub (IOI11_ricehub)C++14
0 / 100
2 ms604 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; int left = 0; int max_len = 0; vector<ll> prefix_vec(n,0); prefix_vec[0] = positions[0]; //calculating prefix sum for(int i = 1; i < n; i++){ prefix_vec[i] = prefix_vec[i-1] + positions[i]; } //sliding window concepts for(int right = 0; right < n; right++){ int median = left + (right-left)/2; ll left_cost = median > 0?((ll)(median-left)*positions[median] - (prefix_vec[median-1] - (left > 0)?prefix_vec[left-1]:0)):0; ll right_cost = (prefix_vec[right] - prefix_vec[median]) - (ll)(right - median)*positions[median]; int currentCost = left_cost + right_cost; while(currentCost > B && median >= left){ left++; median = left + (right-left)/2; left_cost = median > 0?((ll)(median-left)*positions[median] - (prefix_vec[median-1] - prefix_vec[left-1])):0; right_cost = (prefix_vec[right] - prefix_vec[median]) - (right - median)*positions[median]; currentCost = left_cost + right_cost; } max_len = max(max_len,right-left+1); } return max_len; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...