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 <bits/stdc++.h>
#include "ricehub.h"
//#define int long long
using namespace std;
int besthub(int R, int L, int X[], long long B){
long long pref[R+1];
pref[0]=0;
for(int i=1;i<=R;i++)pref[i]=pref[i-1]+X[i];
int ans=0;
map<int,int>cnt;
for(int i=1;i<=R;i++)cnt[X[i]]++;
for(int i=1;i<=R;i++){
long long LL=0LL,RR=(long long)1e15,P=0;
while(LL<=RR){
long long s=(LL+RR)/2;
long long c=0;
for(int j=1;j<=R;j++){
if(X[j]>=X[i]&&X[j]<=X[i]+s){
c+=X[j]-X[i];
}
else if(X[j]<=X[i]&&X[j]>=X[i]-s&&X[j]<=X[i]){
c+=X[i]-X[j];
}
}
/*
int l=1,r=i,p=-1;
while(l<=r){
int mid=(l+r)/2;
if(abs(X[mid]-X[i])<=s){
r=mid-1;
p=mid;
}
else {
l=mid+1;
}
}
int x=i-p+1;
c+=X[i]*x-(pref[i]-pref[p-1]);
l=i+1,r=R,p=-1;
while(l<=r){
int mid=(l+r)/2;
if(abs(X[i]-X[mid])<=s){
l=mid+1;
p=mid;
}
else {
r=mid-1;
}
}
if(p!=-1){
x=p-i;
c+=(pref[p]-pref[i])-X[i]*x;
}*/
if(c<=B){
LL=s+1;
P=s;
}
else {
RR=s-1;
}
//cout<<i<<" "<<s<<" "<<c;
//cout<<endl;
}
int u=0;
long long s=0;
for(int j=1;j<=R;j++){
if(abs(X[i]-X[j])<=P)s+=abs(X[i]-X[j]);
if(abs(X[i]-X[j])<=P)u++;
}
for(int j=1;j<=R;j++){
if(abs(X[i]-X[j])==P+1){
s+=abs(X[i]-X[j]);
if(s<=B)u++;
}
}
/*
int l=1,r=i,p=-1;
while(l<=r){
int mid=(l+r)/2;
if(abs(X[mid]-X[i])<=P){
r=mid-1;
p=mid;
}
else {
l=mid+1;
}
}
s+=((i-p+1)*X[i])-(pref[i]-pref[p-1]);
u+=i-p+1;
l=i+1,r=R,p=-1;
while(l<=r){
int mid=(l+r)/2;
if(abs(X[mid]-X[i])<=P){
l=mid+1;
p=mid;
}
else {
r=mid-1;
}
}
if(p!=-1){
u+=p-i;
s+=(pref[p]-pref[i])-X[i]*(p-i);
}*/
// |x-y|=P
//! kolko ih ima na intervalu [a[i],a[i]+mid]+[a[i]-mid,a[i]]
for(int j=1;j<=R;j++){
if(abs(X[j]-X[i])==P+1){
s+=abs(X[j]-X[i]);
if(s<=B)u++;
}
}
//cout<<i<<" "<<u<<" "<<s;
//cout<<endl;
ans=max(ans,u);
}
return ans;
}/*
signed main(){
int X[4]={0,10,12,14};
cout<<besthub(3,14,X,6);
}*/
/*
1 3 6
2 3 4
3 3 6
3
*/
# | 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... |