06/04/2025 18:15:10

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

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

Задачи

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

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

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

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

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

Задачи

2810. Лагерь ахейцев

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

С той стороны частокол заостренный над ним поднимался, –
Крепкий, высокий, который воздвигли ахейские мужи,
Чтобы служил им надежной защитою против троянцев.
$\ \ \ \ \ \ \ \ \ \ \ \ \ \$ Илиада, песнь 12

Ахейцы, высадившиеся под Троей, окружили свой лагерь стеной из $N$ последовательных участков разной высоты. Афина поведала своему любимцу Одиссею, что вскоре на лагерь нападут $M$ отрядов троянцев, каждый из которых имеет численность $K_i$ и силу $P_i$ . Отряд численностью $K_i$ атакует одновременно $K_i$ подряд идущих участков стены, и если суммарная высота этих участков окажется меньше $P_i$ – троянцы прорвутся в лагерь и сожгут ахейские корабли. Но даже Афина не может заранее предсказать, какие именно участки стены троянцы выберут для атаки. Поэтому Одиссею нужно срочно надстроить стену так, чтобы избежать поражения ахейцев в любом случае. Суммарная высота надстраиваемых частей должна быть минимальной, чтобы Одиссей как можно скорее закончил постройку и вернулся к привычным пирам и состязаниям.

В первой строке ввода указаны два целых числа: длина стены $N$ ( $1<=N<=10^4$ ) и количество атакующих отрядов $M$ ( $1<=M<=10^3$ ). Следующая строка содержит $N$ целых чисел $h_j$ : высоты последовательных участков стены ( $0<=h_j<=10^9$ ). Затем следуют $M$ строк, содержащих описания атакующих отрядов, по два целых числа в каждой: численность отряда $K_i$ ( $1<=K_i<=N$ ) и сила отряда $P_i$ ( $1<=P_i<=10^9$ ).

Выведите единственное целое число – минимальную суммарную высоту надстроек.

Пример ввода

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

Пояснение: участки стены после надстройки будут иметь высоты 2, 4, 2, 3, 2. Соответственно, общая высота надстроек равна 1 + 0 + 2 + 2 + 1 = 6.

29/09/2024	Очный тур личного первенства по спортивному программированию ( 2)
30/09/2024	Дорешивание личных соревнований (2+ курсы) (проводит BOGAT) (H)