Submission #1022565

#TimeUsernameProblemLanguageResultExecution timeMemory
1022565socpiteRice Hub (IOI11_ricehub)C++14
0 / 100
38 ms860 KiB
#include "ricehub.h" #include<bits/stdc++.h> using namespace std; const int maxn = 1e5+5; const int INF = 1e9+5; int A[maxn]; long long pfx[maxn]; int besthub(int R, int L, int X[], long long B) { int ans = 0; for(int i = 1; i <= R; i++){ A[i] = X[i-1]; pfx[i] = pfx[i-1] + A[i]; } for(int i = 1; i <= R; i++){ int l = 0, r = INF; while(l < r){ int mid = (l+r+1)>>1; long long sum = 0; int pl = lower_bound(A+1, A+R+1, A[i] - mid) - A - 1; sum += 1LL*A[i]*(i - pl) - (pfx[i] - pfx[pl]); int pr = upper_bound(A+1, A+R+1, A[i]+mid) - A - 1; sum += (pfx[pr] - pfx[i-1]) - 1LL*A[i]*(pr - (i-1)); if(sum <= B)l = mid; else r = mid-1; } if(l == INF)return R; int mid = l; long long sum = 0; int pl = lower_bound(A+1, A+R+1, A[i] - mid) - A - 1; sum += 1LL*A[i]*(i - pl) - (pfx[i] - pfx[pl]); int pr = upper_bound(A+1, A+R+1, A[i]+mid) - A - 1; sum += (pfx[pr] - pfx[i-1]) - 1LL*A[i]*(pr - (i-1)); ans = max<long long>(ans, pr - pl + (B - sum)/l); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...