Submission #1038563

#TimeUsernameProblemLanguageResultExecution timeMemory
1038563ArthuroWichRice Hub (IOI11_ricehub)C++17
100 / 100
19 ms4500 KiB
#include "ricehub.h" #include<bits/stdc++.h> using namespace std; int besthub(int n, int L, int x[], long long int B) { long long int ans = 0, h = x[0], s = 0, l = 0, r = 1; deque<long long int> left, right; for (long long int i = 1; i < n; i++) { if (s+abs(x[i]-x[0]) <= B) { s += abs(x[i]-x[0]); right.push_back(x[i]); r = i; } } ans = right.size()+1; for (long long int i = 1; i < n; i++) { long long int diff = abs(x[i]-h); left.push_back(h); s += left.size()*diff; s -= right.size()*diff; if (!right.empty()) { right.pop_front(); } h = x[i]; while(!left.empty() && s > B) { s -= abs(left.front()-h); left.pop_front(); l++; } if (r < i || right.empty()) { r = i; } while(!left.empty() && r+1 < n && abs(h-left.front()) >= abs(h-x[r+1])) { s = s-abs(h-left.front())+abs(h-x[r+1]); left.pop_front(); right.push_back(x[r+1]); l++; r++; } while(r+1 < n && s+abs(h-x[r+1]) <= B) { s += abs(h-x[r+1]); right.push_back(x[r+1]); r++; } if (left.empty()) { l = i; } while(l-1 >= 0 && s+abs(h-x[l-1]) <= B) { s += abs(h-x[l-1]); left.push_back(x[l-1]); l--; } ans = max(ans, (long long int) left.size() + (long long int) right.size() + 1); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...