06/04/2025 12:20:11

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

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

Задачи

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

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

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

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

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

Задачи

44. Гангстеры

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

$N$ гангстеров собираются в ресторан.

$i$ -й гангстер приходит в момент времени

$T_i$ и имеет богатство

$P_i$ . Дверь ресторана имеет

$K\ +\ 1$ степень открытости, они обозначаются целыми числами из интервала

$[0,\ K]$ . Степень открытости двери может изменяться на единицу в единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же состоянии. В начальный момент времени дверь закрыта (степень открытости 0).

$i$ -й гангстер заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери соответствует его полноте

$S_i$ . Если в момент, когда гангстер подходит к ресторану, степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени

$[0,\ T]$ . Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.

Ограничения:

$1\ ≤\ N\ ≤\ 100$ ,

$1\ ≤\ K\ ≤\ 100$ ,

$1\ ≤\ T\ ≤\ 30\ 000$ ,

$0\ ≤\ T_i\ ≤\ T$ ,

$1\ ≤\ P_i\ ≤\ 300$ ,

$1\ ≤\ S_i\ ≤\ K$ , все числа целые.

Ввод

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

$N$ ,

$K$ ,

$T$ , во второй –

$T_1,\ T_2,\ …,\ T_N$ , в третьей –

$P_1,\ P_2,\ …,\ P_N$ . в четвёртой –

$S_1,\ S_2,\ …,\ S_N$ . Числа в строках разделены пробелами.

Вывод

Вывести одно число – максимальное суммарное богатство гангстеров, попавших в ресторан. Если зайти не удалось никому, вывести 0.

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

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

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

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

Источник: NEERC, 1998

03/07/2006	Лето 2006 дорешивание ( 4C)
10/07/2006	Лето 2006 - 4 (C)
17/10/2007	Занятие 6 (дорешивание) (B+)
18/10/2008	Занятие 5 (D)
25/02/2013	Занятие 18 (B)
06/07/2020	Летние сборы - 4 (A)