Подразделы

Другие разделы

Дата и время

09/04/2025 08:21:48

Авторизация

Динамическое программирование

And Then There Was One Broken Sword: потерянный файл Decoding Morse Sequences SMS Бросание кубика Витрина Возрастающая подпоследовательность Гангстеры Головоломка умножения Зоопарк Копилка Кубический метр Маршрут Палиндром Разложение на простые слагаемые Скобки (3) Скобки (4) Сообщение Строки Фибоначчи

Гангстеры

Ограничения: время – 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