HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Гангстеры

Section problems

• Всё и сразу
• Всё как у людей
• Все любят уравнения
• Все любят уравнения
• Все любят уравнения
• Второй максимум последовательности
• Выбирайте типы данных с умом
• Вычёркивание
• Гангстеры
• Где ключи?
• Геймер
• Генератор случайных чисел
• Граф
• Граф
• Даты: вчера и завтра
• Даты: интервал между датами
• Даты: конструктор

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Автор: Фёдор Меньшиков, ВГПУ. Difficulty Beta

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