| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 655638 | 2022-11-05T04:09:58 Z | horiseun | 쌀 창고 (IOI11_ricehub) | C++11 | 0 ms | 0 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
#define ll long long
int r, l;
vector<int> x;
vector<ll> pref;
ll b;
ll calc(int length) {
ll val = LLONG_MAX;
for (int i = length - 1; i < r; i++) {
int start = i - length + 1;
int pos = (i + i - length + 1) / 2;
val = min(val, (pos - start) * x[pos] - (pref[pos] - pref[start]) + (pref[i + 1] - pref[pos + 1]) - (i - pos) * x[pos]);
}
return val;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> r >> l >> b;
for (int i = 0; i < r; i++) {
int v; cin >> v;
x.push_back(v);
}
pref.push_back(0);
for (int i = 0; i < r; i++) {
pref.push_back(pref[i] + x[i]);
}
int low = 0, upp = r + 1;
while (low + 1 != upp) {
int mid = (low + upp) / 2;
if (calc(mid) <= b) low = mid;
else upp = mid;
}
cout << low << "\n";
}