Submission #104892

#TimeUsernameProblemLanguageResultExecution timeMemory
104892popovicirobertRice Hub (IOI11_ricehub)C++14
49 / 100
291 ms3064 KiB
#include "ricehub.h" #include <bits/stdc++.h> #define ll long long using namespace std; vector <ll> sp; vector <int> x; inline pair <ll, int> check(int dst, int R, int pos) { int l = 0, r = 0; for(int step = 1 << 16; step; step >>= 1) { if(l + step <= R && x[pos] - dst > x[l + step]) { l += step; } if(r + step <= R && x[pos] + dst >= x[r + step]) { r += step; } } pair <ll, int> ans; ans.first = 1LL * (pos - l) * x[pos] - (sp[pos] - sp[l]) + (sp[r] - sp[pos]) - 1LL * (r - pos) * x[pos]; ans.second = r - l; return ans; } int besthub(int R, int L, int X[], long long B) { x.resize(R + 1), sp.resize(R + 1); for(int i = 1; i <= R; i++) { x[i] = X[i - 1]; sp[i] = sp[i - 1] + x[i]; } ll ans = 0; for(int i = 1; i <= R; i++) { int dst = -1; for(int step = 1 << 30; step; step >>= 1) { if(check(dst + step, R, i).first < B) { dst += step; } } auto cur = check(dst, R, i); dst++; ans = max(ans, cur.second + (B - cur.first) / dst); //cerr << i << " " << cur.first << " " << cur.second << " " << dst << "\n"; } ans = min(ans, 1LL * R); return (int) 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...