Submission #1003230

#TimeUsernameProblemLanguageResultExecution timeMemory
1003230HasanV11010238Rice Hub (IOI11_ricehub)C++17
0 / 100
2 ms604 KiB
/*#include "ricehub.h" #include <bits/stdc++.h> #define ll long long using namespace std; vector<ll> pr, x; ll check(ll l, ll r, ll mid){ int st = l, en = r, be = -1; while (st <= en){ int mi = (st + en) / 2; if (x[mi] <= mid){ st = mi + 1; be = mi; } else{ en = mi - 1; } } ll su = mid * (be - l + 1) - (pr[be] - pr[l - 1]); su += (pr[r] - pr[be]) - mid * (r - be + 1); return su; } int besthub(int R, int L, int X[], long long B) { pr.assign(R + 1, 0), x.assign(R + 1, 0); for (int i = 1; i <= R; i++){ x[i] = X[i - 1]; pr[i] = pr[i - 1] + x[i]; } ll l = 1, r = 1, ans = 0; while(r <= R){ int mid = (x[l] + x[r]) / 2, mi1, mi2; auto it = upper_bound(x.begin(), x.end(), mid); if (it == x.end()){ mi1 = mi2 = R; } else{ mi2 = it - x.begin(); mi1 = mi2 - 1; } ll va = min(check(l, r, mi1), check()) } return ans; }*/ #include "ricehub.h" #include <bits/stdc++.h> #define ll long long using namespace std; vector<ll> pr, x; ll check(ll l, ll r, ll mid){ int st = l, en = r, be = -1; while (st <= en){ int mi = (st + en) / 2; if (x[mi] <= mid){ st = mi + 1; be = mi; } else{ en = mi - 1; } } ll su = x[be] * (be - l + 1) - (pr[be] - pr[l - 1]); su += (pr[r] - pr[be]) - x[be] * (r - be + 1); return su; } int besthub(int R, int L, int X[], long long B) { pr.assign(R + 1, 0), x.assign(R + 1, 0); for (int i = 1; i <= R; i++){ x[i] = X[i - 1]; pr[i] = pr[i - 1] + x[i]; } ll l = 1, r = 1, ans = 0; while(r <= R){ if ((x[r] + x[l]) % 2 == 1){ int mi1 = (x[l] + x[r]) / 2, mi2 = (x[l] + x[r]) / 2 + 1; ll va1 = check(l, r, mi1), va2 = check(l, r, mi2); if (va1 > va2){ swap(va1, va2); } if (va1 > B){ l++; } else if (va1 <= B){ r++; ans = max(ans, (r - l)); } } else{ int mi = (x[l] + x[r]) / 2; ll va = check(l, r, mi); if (va > B){ l++; } else{ r++; ans = max(ans, (r - 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...