This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
long long sumf[100005];
long long sumb[100005];
long long n;
int am;
vector<long long>v;
long long cost;
pair<int,long long> tl(int i,int r,long long mx,long long left){
int en=r;
int st=0;
int ans=r+1;
//cout<<"mx:"<<mx<<endl;
while(st<=en){
int m=(st+en)/2;
//cout<<"m:"<<m<<" "<<v[i]-v[m]<<" "<<sumb[m]-sumb[r+1]<<"-"<<(r-m+1)<<"*"<<n<<"-"<<v[r+1]<<endl;
if(v[i]-v[m]<=mx&&(sumb[m]-sumb[r+1])-(r-m+1)*(n-v[r+1])<=left){
ans=m;
en=m-1;
}else{
st=m+1;
}
}
//cout<<"r:"<<r<<endl;
//cout<<ans<<":"<<left<<"-"<<"("<<sumb[ans]-sumb[r+1]<<"-"<<r+1-ans<<"*"<<n-v[r+1]<<")"<<endl;
return {ans,left-((sumb[ans]-sumb[r+1])-(r+1-ans)*(n-v[r+1]))};
}
pair<int,long long> tr(int i,int l,long long mx,long long left){
int en=am-1;
int st=l;
int ans=l-1;
while(st<=en){
int m=(st+en)/2;
//cout<<"m:"<<m<<endl;
//cout<<(sumf[m]-sumf[l-1])-(m-l+1)*(v[l-1])<<endl;
if(v[m]-v[i]<=mx&&(sumf[m]-sumf[l-1])-(m-l+1)*(v[l-1])<=left){
ans=m;
st=m+1;
}else{
en=m-1;
}
}
return {ans,left-((sumf[ans]-sumf[l-1])-(ans-l+1)*(v[l-1]))};
}
int cnl=0,cnr=0;
int fr(int i){
//cout<<"I:"<<i<<endl;
long long left=cost;
//cout<<"left:"<<cost<<endl;
int l=i+1,r=i-1;
bool cl;
if(i==0){
cl=1;
}else if(i==am-1){
cl=0;
}else{
cl=v[i]-v[i-1]<v[i+1]-v[i];
}
cnl=0,cnr=0;
//cout<<"right, left:"<<r<<" "<<l<<endl;
while(left>=0){
if(cl){
//cout<<"going left"<<endl;
long long mx;
if(l<am){
mx=v[l]-v[i];
}else{
mx=LLONG_MAX;
}
pair<int,int> move=tl(i,r,mx,left);
left=move.second;
//
if(r==move.first-1){
cnl=1;
}
r=move.first-1;
//cout<<r<<" "<<left<<endl;
}else{
//cout<<"going right"<<endl;
long long mx;
if(r>=0){
mx=v[i]-v[r];
}else{
mx=LLONG_MAX;
}
pair<int,int> move=tr(i,l,mx,left);
left=move.second;
if(l==move.first+1){
cnr=1;
}
l=move.first+1;
//cout<<l<<" "<<left<<endl;
}
//cout<<"result:"<<r<<" "<<l<<endl;
if(cnl&&cnr){
break;
}
cl^=1;
}
//cout<<"final result:"<<r<<" "<<l<<endl;
//cout<<endl;
return l-r-1;
}
int besthub(int r, int l, int x[], long long b)
{
long long sum=0;
cost=b;
n=l;
am=r;
for(int i=0;i<r;i++){
sum+=x[i];
sumf[i]=sum;
v.push_back(x[i]);
}
sum=0;
for(int i=r-1;i>=0;i--){
sum+=l-x[i];
sumb[i]=sum;
}
/*cout<<"info:"<<endl;
for(int i=0;i<r;i++){
cout<<sumb[i]<<" ";
}
cout<<endl;*/
int ans=0;
for(int i=0;i<r;i++){
ans=max(ans,fr(i));
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |