| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 216037 | 2020-03-26T16:35:44 Z | jungsnow | Rice Hub (IOI11_ricehub) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
ll n, l, b, x[N], s1[N], s2[N];
bool ok(ll len) {
if (len & 1) {
int dist = (len - 1) / 2;
for (int i = dist + 1; i <= n - dist; i++) {
ll sum = s1[i] - s1[i - dist] - (i - dist - 1) * (x[i] - x[i - dist]);
ll sum2 = (s2[i] - s2[i + dist] - (n - (i + dist)) * (x[i + dist] - x[i]));
if (sum + sum2 <= b) {
return true;
}
}
} else {
int dist = (len / 2);
for (int i = dist; i <= n - dist; i++) {
if (i < n - dist) {
ll sum = s1[i] - s1[i - dist + 1] - (i - dist) * (x[i] - x[i - dist + 1]);
ll sum2= s2[i] - s2[i + dist] - (n - (i + dist)) * (x[i + dist] - x[i]);
if (sum + sum2 <= b) return true;
}
if (i > dist) {
ll sum = s1[i] - s1[i - dist] - (i - dist - 1) * (x[i] - x[i - dist]);
ll sum2= s2[i] - s2[i + dist - 1] - (n - (i + dist) + 1) * (x[i] - x[i + dist - 1]);
if (sum + sum2 <= b) return true;
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("rice.inp", "r", stdin);
//freopen("rice.out", "w", stdout);
cin >> n >> l >> b;
for (int i = 1; i <= n; i++) cin >> x[i];
for (int i = 2; i <= n; i++) {
s1[i] = s1[i - 1] + (i - 1) * (x[i] - x[i - 1]);
}
for (int i = n - 1; i >= 1; i--) {
s2[i] = s2[i + 1] + (n - i) * (x[i + 1] - x[i]);
}
/* for (int i = 1; i <= n; i++) cout << s1[i] << ' ';
cout << '\n';
for (int i = 1; i <= n; i++) cout << s2[i] << ' '; */
int lo = 1, hi = n, r = 1;
while (lo <= hi) {
int mi = (lo + hi) / 2;
if (ok(mi)) {
lo = mi + 1;
r = mi;
}
else hi = mi - 1;
}
cout << r;
return 0;
}