| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1115581 | vjudge1 | 쌀 창고 (IOI11_ricehub) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int R;
ll L, B;
vector<ll> X;
vector<ll> prefixSum;
bool check(int K) {
int N = R;
for (int i = 0; i <= N - K; ++i) {
int j = i + K - 1;
int m = (i + j) / 2;
int leftCount = m - i;
ll sumLeft = (leftCount > 0 ? prefixSum[m - 1] - (i > 0 ? prefixSum[i - 1] : 0) : 0);
int rightCount = j - m;
ll sumRight = (rightCount > 0 ? prefixSum[j] - prefixSum[m] : 0);
ll totalCost = X[m] * (ll)leftCount - sumLeft + sumRight - X[m] * (ll)rightCount;
if (totalCost <= B) {
return true;
}
}
return false;
}
int main() {
cin >> R >> L >> B;
X.resize(R);
for (int i = 0; i < R; ++i) {
cin >> X[i];
}
prefixSum.resize(R);
prefixSum[0] = X[0];
for (int i = 1; i < R; ++i) {
prefixSum[i] = prefixSum[i - 1] + X[i];
}
int low = 1, high = R;
int ans = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (check(mid)) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << ans << endl;
return 0;
}