| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 895848 | 2023-12-30T22:31:44 Z | vjudge1 | 쌀 창고 (IOI11_ricehub) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
ll n, budget;
vector<ll> psum;
vector<ll> ssum;
bool check(ll rice) {
ll middle = (rice-1) / 2;
ll right = middle+(rice)/2;
ll minb = 1e9;
for (ll i = 0; i <= n - rice; i++) {
ll b = psum[i+right] - psum[i+middle] + ssum[i] - ssum[i+middle];
minb = min(b, minb);
}
//cout << "minb: " << minb << endl;
if (minb <= budget) return true;
return false;
}
void besthub(ll r, ll maxcoor, ll a[], ll b) {
n = r;
budget = b;
ll diff[n-1];
for (ll i = 0; i < n-1; i++) {
diff[i] = a[i+1] - a[i];
}
psum.resize(n, 0);
ssum.resize(n, 0);
for (ll i = 1; i < n; i++) {
psum[i] = a[i-1] + psum[i-1];
}
for (ll i = n-2; i >= 0; i--) {
ssum[i] = a[i] + ssum[i+1];
}
ll l = 1;
while (l < r) {
ll mid = (l + r + 1) / 2;
//cout << "mid: " << mid << endl;
if (check(mid)) {
l = mid;
}
else {
r = mid - 1;
}
}
cout << l << endl;
}
signed main() {
ll r, l, b; cin >> r >> l >> b;
ll x[r];
for (ll i = 0; i < r; i++) cin >> x[i];
besthub(r, l, x, b);
}