Submission #880726

#TimeUsernameProblemLanguageResultExecution timeMemory
880726androRice Hub (IOI11_ricehub)C++14
100 / 100
10 ms3676 KiB
#include<bits/stdc++.h> #include "ricehub.h" using namespace std; using ll = long long; const int N = 100005; ll suf[N], pref[N]; int besthub(int n, int L, int a[], long long c) { if(n==1)return 1; for(int i=1; i<=n; i++){ pref[i]=pref[i-1]+a[i-1]; } for(int i=n-1; i>=0; i--){ suf[i]=pref[n]-pref[i]; } ll sufind=n; ll mx; ll s=n/2; ll cost=2e18; while(cost>c){ s=sufind/2; cost=a[s]*(s+1)-pref[s+1]-a[s]*(sufind-s)+suf[s]-suf[sufind]; if(cost<=c)break; sufind--; } mx=sufind; for(int i=1; i< n; i++){ cost=0; while(cost<=c && sufind<n){ s=(sufind+i)/2; cost=a[s]*(s-i+1)-pref[s+1]+pref[i]-a[s]*(sufind-s)+suf[s+1]-suf[sufind+1]; sufind++; } if(sufind==n && cost<=c){ mx=max(mx, sufind-i); break; } else{ sufind--; mx=max(mx, sufind-i); } } return mx; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...