Submission #880560

#TimeUsernameProblemLanguageResultExecution timeMemory
880560androRice Hub (IOI11_ricehub)C++14
68 / 100
1062 ms984 KiB
#include <bits/stdc++.h> #include "ricehub.h" //#define int long long using namespace std; const int N=1e6+5; struct fenw{ int t[N]; int query(int i){int ans=0;for(;i>0;i-=i&-i)ans+=t[i];return ans;} void update(int i,int v){for(;i<N;i+=i&-i)t[i]+=v;} int query(int l,int r){return query(r)-query(l-1);} }; int besthub(int R, int L, int X[], long long B){ int ans=0; for(int i=1;i<=R;i++){ vector<int>v; for(int j=1;j<=R;j++)v.push_back(abs(X[i]-X[j])); long long l=0LL,r=100000000000LL,p=0; while(l<=r){ long long mid=(l+r)/2; long long c=0; for(int j=1;j<=R;j++){ if(X[j]>=X[i]&&X[j]<=X[i]+mid){ c+=X[j]-X[i]; } else if(X[j]<=X[i]&&X[j]>=X[i]-mid&&X[j]<=X[i]){ c+=X[i]-X[j]; } } if(c<=B){ l=mid+1; p=mid; } else { r=mid-1; } } int u=0; long long c=0; for(int j=1;j<=R;j++){ if(abs(X[i]-X[j])<=p)c+=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){ c+=abs(X[i]-X[j]); if(c<=B)u++; } } //! kolko ih ima na intervalu [a[i],a[i]+mid]+[a[i]-mid,a[i]] ans=max(ans,u); } return ans; }/* signed main(){ int X[4]={0,10,12,14}; cout<<besthub(3,14,X,6); }*/ /* 1 3 2 3 3 3 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...