Submission #261544

#TimeUsernameProblemLanguageResultExecution timeMemory
261544sandovalRice Hub (IOI11_ricehub)C++11
17 / 100
1092 ms1536 KiB
#include "ricehub.h" #include <bits/stdc++.h> using namespace std; using ll = long long; int besthub(int R, int L, int X[], long long B) { const int n = R; vector<ll> pre(X, X+n); for (int i = 1; i < n; ++i) pre[i] += pre[i-1]; auto sum = [](const vector<ll>& ps, int l, int r)->long long{ if (l > r) return 0LL; ll ans = ps[r]; if (l > 0) ans -= ps[l-1]; return ans; }; auto get = [&sum](int l, int r, const vector<ll>& ps, int a[], ll p)->long long{ int idx = upper_bound(a+l, a+r+1, p) - a; int g = max(0, 1+r-idx); int le = max(0, idx-l); ll ans = 0; for (int i = l; i <= r; ++i) ans += abs(p-a[i]); assert(ans == p*1LL*le-sum(ps,l,idx-1)+sum(ps,idx,r)-1LL*g*p); return p*1LL*le-sum(ps,l,idx-1)+sum(ps,idx,r)-1LL*g*p; }; auto cost = [&get, &sum](int l, int r, const vector<ll>& ps, int x[])->long long{ long long av = sum(ps, l, r)/ll(1+r-l); int idx = upper_bound(x+l, x+r+1, av) - x; int op1 = idx-1; int op2 = idx; ll a = numeric_limits<ll>::max(); ll b = numeric_limits<ll>::max(); if (op1 >= l && op1 <= r) { a = get(l, r, ps, x, x[op1]); } if (op2 >= l && op2 <= r) { b = get(l, r, ps, x, x[op2]); } return min(a,b); }; int ans = 1; for (int i = 0; i < n; ++i) { int low = i, high = n-1, best = -1; while (low <= high) { int mid = (low+high) >> 1; if (cost(i,mid,pre,X) <= B) { low = 1+mid; best = mid; } else { high = mid-1; } } assert(best >= i && best < n); ans = max(ans, 1+best-i); } 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...