| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 684354 | kusssso | 쌀 창고 (IOI11_ricehub) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
ll f[N];
bool check (ll x, ll b, int l, int r, vector<ll> &a) {
int j = upper_bound(a.begin(), a.end(), x) - a.begin();
j = min(j, r - 1);
ll sum = x * (j - l + 1) - (f[j] - f[l - 1]) + (f[r] - f[j]) - x * (r - j);
// if (x == 8 && l == 2 && r == 5) {
// cout << f[r]- f[j] << '\n';
// cout << j + 1 << ' ' << sum << '\n';
// cout << (sum <= b) << '\n';
// }
return (sum <= b);
}
bool ok (int k, ll b, int n, vector<ll> &a) {
for (int i = k; i <= n; i++) {
ll med = (f[i] - f[i - k]) / k;
if (check(med, b, i - k + 1, i, a)) {
// if (k == 4) {
// cout << i - k + 1 << ' ' << i << '\n';
// }
return true;
}
if (check(med + 1, b, i - k + 1, i, a)) {
// if (k == 4) {
// cout << i - k + 1 << ' ' << i << '\n';
// }
return true;
}
if (check(med - 1, b, i - k + 1, i, a)) {
// if (k == 4) {
// cout << i - k + 1 << ' ' << i << ' ' << med - 1 << '\n';
// }
return true;
}
}
return false;
}
int besthub (int r, int l, vector<ll> x, ll b) {
for (int i = 0; i < r; i++) {
f[i + 1] = f[i] + x[i];
}
int ans = -1;
int lo = 0, hi = r;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (ok(mid, b, r, x)) {
ans = mid;
lo = mid + 1;
}
else {
hi = mid - 1;
}
}
return ans;
}
// signed main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
//
// cout << besthub(5, 20, {1, 2, 10, 12, 14}, 6);
//
// return 0;
// }