| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 38 | 9 | 5 | 14.706% |
Вдоль прямой дороги, на которой происходят испытания беспилотных грузовиков, расположены $n$ городов, $i$-й город находится в точке, имеющей координату $i$. В $i$-м городе установлена антенна мощностью $a_i$, покрывающая все города от $L_i = \max\left(1, i - a_i\right)$ до $R_i = \min(n, i + a_i)$ включительно.
Беспилотный грузовик перемещается вдоль дороги от города $s$ к городу $t$, где $s < t$. В каждом городе по пути следования грузовик подключён к одной из антенн. Подключение к антеннам происходит следующим образом.
Обозначим как $f(s, t)$ количество переподключений между антеннами для грузовика, который начинает свой маршрут в городе $s$ и заканчивает свой маршрут в городе $t$ ($s < t$). Начальное подключение к антенне в городе $s$ переподключением не считается.
Нестойкостью покрытия дороги антеннами назовем сумму значений $f(s, t)$ по всем допустимым парам городов, то есть величину $$F= \sum\limits_{s=1}^{n-1} \sum\limits_{t=s+1}^{n} f(s, t). $$
В распоряжении оператора дороги есть одна запасная антенна с мощностью $x$. Для снижения нестойкости покрытия можно заменить одну из антенн на запасную. Требуется определить минимальное значение нестойкости покрытия дороги $F$, если не более одной антенны можно заменить на запасную антенну мощности $x$.
Первая строка содержит два целых числа $n$ и $x$ ($1 \le n \le 10^6$, $0 \le x \le n$) --- количество городов и мощность запасной антенны.
Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n$) --- мощности антенн.
Выведите минимальное возможное значение нестойкости покрытия дороги, если не более одной антенны можно заменить на запасную антенну мощности $x$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $n \leq 100$ |
| 2 | 8 | $n \leq 500$ |
| 3 | 6 | $n \leq 5000$ |
| 4 | 12 | $x = 0$ |
| 5 | 5 | $a_{i} = 0$ |
| 6 | 16 | $a_{i} \leq 1$ |
| 7 | 14 | $a_{i} \geq \frac{n}{20}$ |
| 8 | 32 |
3 1 1 0 0
0
5 0 2 1 0 0 1
6
В первом примере мы можем заменить вторую антенну на запасную. Тогда грузовик, стартующий в любой точке, будет подключаться к ней и переподключаться никакому грузовику не понадобится.
Во втором примере использовать запасную антенну не нужно. Грузовикам, стартующим в одном из первых трёх городов и финиширующим в одном из двух последних городов придётся один раз переподключиться к последней антенне, поэтому нестойкость покрытия дороги равна 6.