10/04/2025 23:08:23

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2242. Шушпанчики и кинотеатр

Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В кинотеатре "Дружба" через неделю пройдет премьера мирового хита "Осторожный Макс", и шушпанчики обязательно хотят попасть на первый сеанс. Зал в кинотеатре состоит из

$n$ рядов по

$n$ мест в каждом. Ряды пронумерованы от 1 до

$n$ , места в каждом ряду также пронумерованы от 1 до

$n$ . Обозначим место с номером

$c$ в ряду

$r$ как

$(r,\ c)$ .

Шушпанчики точно знают, что лучшее место в зале – место

$(r_b,\ c_b)$ . Для любого места

$(r,\ c)$ можно посчитать неудачность этого места как

$|r-r_b|+|c-c_b|$ , и чем неудачность меньше, тем лучше.

Шушпанчики пойдут на сеанс группой из

$k$ шушпанчиков. Они хотят сидеть рядом друг с другом, поэтому договорились купить

$k$ мест подряд в одном ряду. Таким образом, шушпанчики купят билеты на места

$(r_a,\ c_a),\ (r_a,\ c_a+1),\ …,\ (r_a,\ c_a+k-1)$ для некоторых

$r_a$ и

$c_a$ .

К сожалению, некоторые места уже забронированы, и их выкупить не получится. Помогите шушпанчикам выбрать

$k$ соседних мест на одном ряду так, чтобы суммарная неудачность выбранных ими мест была минимальна.

В первой строке заданы три числа

$n$ ,

$m$ и

$k$ (

$1\ ≤\ n\ ≤\ 10^9$ ,

$0\ ≤\ m\ ≤\ min(n^2,\ 10^5)$ ,

$1\ ≤\ k\ ≤\ n$ ) – размер зала, число проданных мест и число шушпанчиков.

В следующих

$m$ строках описаны занятые места. Каждое место описывается двумя числами:

$r_i,\ c_i$ (

$1\ ≤\ r_i,\ c_i\ ≤\ n$ , все описанные места различны).

В следующей строке даны два числа

$r_b,\ c_b$ (

$1\ ≤\ r_b,\ c_b\ ≤\ n$ ) – оптимальное место, как можно ближе к которому хотят оказаться шушпанчики.

Если все шушпанчики не смогут купить билеты на

$k$ мест подряд в одном ряду, выведите

$-1$ . Иначе, выведите минимальную суммарную неудачность, которую можно получить.

Пример ввода 1

3 1 2
1 2
1 1

Пример вывода 1

Пример ввода 2

Пример вывода 2

-1

Источник: XXIII Командный чемпионат школьников Санкт-Петербурга по программированию, 2015