#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
typedef long long ll;
ll linf = 1e15+1;
inline void scoobydoobydoo(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
}
const int MAXN = 2e5+1;
ll farms[MAXN];
ll pref[MAXN];
ll n, nmax;
ll budget;
ll calc(ll point, ll l, ll r){
ll howR = r-point;
ll right = pref[r]-pref[point]-howR*farms[point];
ll howL = point-l;
ll left = howL*farms[point]-pref[point-1]+(l == 0 ? 0 :pref[l-1]);
return right+left;
}
bool works(int di){
int l = 0, r = di-1;
ll mid = 0;
ll mini = 1e15;
ll lowest = 1e15;
for (int i = 0; i <= r; i++){
ll sum = calc(i, l, r);
if (sum < mini){
mini = sum;
mid = i;
}
}
lowest = min(lowest, mini);
//cout << "low: " << lowest << " " << mid << endl;
while (r < n-1){
l++; r++;
while (calc(mid+1, l, r) <= calc(mid, l, r)){
mid++;
}
lowest = min(lowest, calc(mid, l, r));
//cout << "low: " << lowest << " " << mid << endl;
}
//cout << di << " " << lowest << endl;
return lowest <= budget;
}
ll besthub(ll R, ll L, ll X[], ll B){
n = R;
nmax = L+1;
budget = B;
for (int i = 0; i < n; i++){
farms[i] = X[i];
pref[i] = farms[i] + (i != 0 ? pref[i-1] : 0);
}
ll a = 0, b = n+1;
ll ret = 0;
while (a < b){
ll k = (a+b)>>1;
if (works(k)){
ret = k;
a = k+1;
} else b = k;
}
return ret;
}
Compilation message
/usr/bin/ld: /tmp/ccRqcoE4.o: in function `main':
grader.cpp:(.text.startup+0xae): undefined reference to `besthub(int, int, int*, long long)'
collect2: error: ld returned 1 exit status
