#include<bits/stdc++.h>
#define ll long long int
#define ff first
#define ss second
#define FOR(i,N) for(i=0;i<N;i++)
#define FORe(i,N) for(i=1;i<=N;i++)
#define FORr (i,a,b) for(i=a;i<b;i++)
#define vi vector <ll>
#define ii pair<ll,ll>
#define vii vector<ii>
#define mp make_pair
#define pb push_back
#include "ricehub.h"
using namespace std;
/*
const ll MAXN = 1e5+ 4;
const ll LOGN = 17;
const ll ROOTN = 320;
const ll MOD = 1e9+7;
const ll INF = 1e17+8;
*/
inline ll cost(ll N,ll X[],ll num)
{
//cout<<"getting in for num = "<<num<<endl;
ll i,j,k,sum = 0,ans;
FOR(i,num)
sum += X[i] - X[0];
ans = sum;
//cout<<"precomputed ans = "<<ans<<endl;
i = 0;
j = num - 1;
k = 1;
while(k < N)
{
//cout<<"entered while loop for i = "<<i<<"; j = "<<j<<"; k = "<<k<<endl;
sum += (k - i)*(X[k] - X[k-1]) - (j - k + 1)*(X[k] - X[k-1]);
if (k > j)
{
j++;
i++;
sum -= X[k]-X[i-1];
}
while(j < N-1 and i < k and (X[j+1] - X[k]) < (X[k] - X[i]))
{
sum += (X[j+1] - X[k]) - (X[k] - X[i]);
j++;
i++;
}
//cout<<"calculated sum = "<<sum<<endl;
ans = min(sum,ans);
k++;
}
return ans;
}
long long besthub(ll R,ll L,ll X[],ll B)
{
ll hi = R,lo = 1,mid = 0;
if (cost(R,X,R) <= B)
return R;
while(lo < hi-1)
{
mid = (hi+lo)/2;
if (cost(R,X,mid) > B)
hi = mid;
else
lo = mid;
}
return lo;
}
/*
int main()
{
/*
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
*/
ll L,B,R;
cin>>R>>L;
ll i,X[R];
FOR(i,R)
cin>>X[i];
cin>>B;
cout<<besthub(R,L,X,B);
return 0;
}
*/
Compilation message
ricehub.cpp:79:2: warning: "/*" within comment [-Wcomment]
/*
ricehub.cpp:85:2: error: 'cin' does not name a type; did you mean 'sin'?
cin>>R>>L;
^~~
sin
ricehub.cpp:86:10: error: array bound is not an integer constant before ']' token
ll i,X[R];
^
ricehub.cpp:6:18: error: expected unqualified-id before 'for'
#define FOR(i,N) for(i=0;i<N;i++)
^
ricehub.cpp:87:2: note: in expansion of macro 'FOR'
FOR(i,R)
^~~
ricehub.cpp:87:6: error: 'i' does not name a type
FOR(i,R)
^
ricehub.cpp:6:26: note: in definition of macro 'FOR'
#define FOR(i,N) for(i=0;i<N;i++)
^
ricehub.cpp:87:6: error: 'i' does not name a type
FOR(i,R)
^
ricehub.cpp:6:30: note: in definition of macro 'FOR'
#define FOR(i,N) for(i=0;i<N;i++)
^
ricehub.cpp:89:2: error: 'cin' does not name a type; did you mean 'sin'?
cin>>B;
^~~
sin
ricehub.cpp:90:2: error: 'cout' does not name a type; did you mean 'cost'?
cout<<besthub(R,L,X,B);
^~~~
cost
ricehub.cpp:91:2: error: expected unqualified-id before 'return'
return 0;
^~~~~~
ricehub.cpp:92:1: error: expected declaration before '}' token
}
^
