ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Фёдор Меньшиков. Тренировки > задача:


04C. Гангстеры

Задачи сборника

• 01C. Возрастающая последовател...
• 01D. Треугольник и точка
• 02A. Простые числа (2)
• 02E. Длинная сумма
• 03D. Открытка и конверт
• 03E. Длинное произведение
• 04A. Совершенные числа
• 04B. Разложение на слагаемые
• 04C. Гангстеры
• 04D. Площадь многоугольника
• 04E. Деление длинного числа на к...
• 04F. Скобки
• 03C. Копилка
• 05E. Системы счисления

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Фёдор Меньшиков, ВГПУ. Сложность Бета

N гангстеров собираются в ресторан. i-й гангстер приходит в момент времени Ti и имеет богатство Pi. Дверь ресторана имеет K + 1 степень открытости, они обозначаются целыми числами из интервала [0, K]. Степень открытости двери может изменяться на единицу в единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же состоянии. В начальный момент времени дверь закрыта (степень открытости 0). i-й гангстер заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери соответствует его полноте Si. Если в момент, когда гангстер подходит к ресторану, степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0, T]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.

Ввод
В первой строке находятся числа N, K, T, во второй - T1, T2, ..., TN, в третьей - P1, P2, ..., PN. в четвёртой - S1, S2, ..., SN. Числа в строках разделены пробелами.
Вывод
Вывести одно число - максимальное суммарное богатство гангстеров, попавших в ресторан. Если зайти не удалось никому, вывести 0.
Ограничения
1 ≤ N ≤ 100; 1 ≤ K ≤ 100; 1 ≤ T ≤ 30 000; 0 ≤ TiT; 1 ≤ Pi ≤ 300; 1 ≤ SiK; все числа целые.

Ввод 1 Ввод 2
4 10 20
10 16 8 16
10 11 15 1
10 7 1 8
2 17 100
5 0
50 33
6 1
Вывод 1 Вывод 2
26
0

Для отправки решений необходимо выполнить вход.

www.contester.ru