Submission #1236666

#TimeUsernameProblemLanguageResultExecution timeMemory
1236666fauntleroyRice Hub (IOI11_ricehub)C++20
0 / 100
0 ms324 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; int besthub(int R, int L, int x[], ll B) { int n = R; vector<ll> d(n - 1); for (int i = 0; i < n - 1; ++i) d[i] = x[i + 1] - x[i]; vector<ll> pref(n - 1, 0); pref[0] = d[0]; for (int i = 1; i < n - 1; ++i) pref[i] = pref[i - 1] + d[i]; int l = 0, r = n; int ans = 0; while (l <= r) { int k = (l + r) >> 1; --k; if (k == 0) { ans = max(ans, 1); l = 2; continue; } int l1 = 0, r1 = n - k - 1; ll mn = 1e9; for (int i = 0; i < n - k; ++i) { ll s = pref[i + k - 1] - (i > 0 ? pref[i - 1] : 0); if (s < mn) { l1 = i, r1 = i + k - 1; mn = s; } } //cout << l1 << ' ' << r1 << ' ' << " " << ' ' << k << '\n'; int pos = (l1 > 0 ? pref[l1 - 1] : 0) + 1 + mn / 2; ll d = 0; for (int i = l1; i <= r1 + 1; ++i) d += abs(pos - x[i]); //cout << pos<<' '<<d << '\n'; ++k; if (d > B) r = k - 1; else l = k + 1, ans = max(ans, k); } 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...