| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 552492 | Sharky | 쌀 창고 (IOI11_ricehub) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
int r, l, b;
vector<int> v;
vector<int> ps(N, 0);
bool ok(int L, int R, int x) {
int mid = (L + R) >> 1; // median
// brute force
int cost = v[mid] * (mid - L + 1) - (ps[mid] - ps[L - 1]);
// cout << L << " " << R << " " << mid << " " << cost;
cost += (ps[R] - ps[mid]) - v[mid] * (R - mid);
// cout << " " << cost << "\n";
return (cost <= b);
}
bool check(int x) {
// x consecutive hubs
for (int i = 1; i <= r - x + 1; i++) {
if (ok(i, i + x - 1, x)) return true;
}
return false;
}
int besthub(int rr, int ll, int vv[], long long bb) {
v.push_back(0);
r = rr, l = ll, b = bb;
for (int i = 0; i < vv.size(); i++) { v.push_back(vv[i]); }
int lo = 1, hi = r, ans;
while (lo <= hi) {
int m = (lo + hi) >> 1;
// cout << m << " " << check(m) << "\n";
if (check(m)) lo = m + 1, ans = m;
else hi = m - 1;
}
return ans;
}
