Submission #880715

#TimeUsernameProblemLanguageResultExecution timeMemory
880715androRice Hub (IOI11_ricehub)C++14
0 / 100
1067 ms1628 KiB
#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=i-1;j>=1;j--){ if(abs(X[i]-X[j])>P)break; u++; s+=abs(X[i]-X[j]); } for(int j=i;j<=R;j++){ if(abs(X[i]-X[j])>P)break; u++; s+=abs(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])<=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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...