07/04/2025 03:36:47

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

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

Задачи

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

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

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

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

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

Задачи

2030. Кондиционеры

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

При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.

Все классы школы пронумерованы последовательно от 1 до

$n$ . Известно, что для каждого класса с номером

$i$ , требуется ровно один кондиционер, мощность которого больше или равна

$a_i$ ватт.

Администрации школы предоставили список из

$m$ различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.

Формат входного файла

Первая строка входного файла содержит одно целое число

$n$ (

$1 ≤ n ≤ 50 000$ ) – количество классов в школе.

Вторая строка содержит

$n$ целых чисел

$a_i$ (

$1 ≤ a_i ≤ 1000$ ) – минимальная мощность кондиционера в ваттах, который можно установить в классе с номером

$i$ .

Третья строка содержит одно целое число

$m$ (

$1 ≤ m ≤ 50 000$ ) – количество предложенных моделей кондиционеров.

Далее, в каждой из

$m$ строк содержится пара целых чисел

$b_j$ и

$c_j$ (

$1 ≤ b_j ≤ 1000$ ,

$1 ≤ c_j ≤ 1000$ ) – мощность в ваттах

$j$ -й модели кондиционера и его цена в рублях соответственно.

Формат выходного файла

Выходной файл должен содержать одно число – минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.

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

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

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

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

Пояснения к примерам

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе – кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для

$n, m ≤ 1000$ будут оцениваться из 50 баллов.

Источник: региональный этап Всероссийской олимпиады по информатике 2013/2014, http://neerc.ifmo.ru/school/

03/02/2014	Областная олимпиада школьников по информатике. II тур. (6)
07/07/2023	Лето 2023-6 простые (командное) (F)
07/07/2023	Лето 2023-6 сложные (командное) (E)
05/07/2024	Лето 2024-6 простые (командное) (F)
05/07/2024	Лето 2024-6 сложные (командное) (E)