Задача A. Маршрутка ≡

Автор:unknown
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:200 Мб

Условие

Маршрутное такси на P посадочных мест движется по линии с N остановками, пронумерованными от 1 до N в порядке следования такси. На остановках стоят очереди из пассажиров. Каждый пассажир имеет цель — попасть на некоторую остановку, расположенную дальше по маршруту.

На каждой остановке:

Каждый пассажир платит водителю 5 рублей. На первой остановке, в отличие от остальных, водитель по своему усмотрению ограничивает количество севших пассажиров f. Требуется определить наибольший доход, который может получить водитель, выбрав оптимальное значение f.

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

В первой строке входного файла содержатся числа N и P. В следующих N − 1 строках находятся числа Ki di,1… di,Ki — количество пассажиров на очередной остановке и цель каждого пассажира. (На конечной остановке пассажиры не садятся).

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

Выходной файл должен содержать единственное целое число — максимальный доход водителя в рублях.

Ограничения

2 ≤ N ≤ 50, 1 ≤ P ≤ 20

0 ≤ Ki < P, i < di,j ≤ N

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4 3
2 2 4
3 3 3 3
2 4 4

30

Задача B. Новогодняя ёлка-2 ≡

Автор:И. Олейников
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:4 Мб

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K елочных игрушек.

Елочные игрушки характеризуются двумя параметрами — массой и красотой. Елка также характеризуется двумя параметрами — максимальной массой игрушек, которую она может выдержать и красотой. Красота елки равна сумме красот всех висящих на ней игрушек. Так как дети хотят удивить Деда мороза, они хотят как можно красивее украсить ёлку, при этом она не должна упасть.

Вас просят написать программу, которая по заданным параметрам игрушек и ёлки определит максимально возможную красоту наряженной ёлки.

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

Во входном файле содержатся числа M и K — соответственно максимальная масса игрушек на ёлке и количество купленных игрушек. За ними следуют K пар чисел vi ki соответственно вес и красота i-той игрушки.

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

В выходном файле должно содержаться единственное число - максимально возможная красота наряженной ёлки.

Ограничения

1 ≤ K, M ≤ 100 1 ≤ vi, ki ≤ 100

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 2
1 2
2 2
 
4

Задача C. Новогодняя ёлка-3 ≡

Автор:И. Олейников, А Кленин, И Туфанов
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K елочных игрушек.

Елочные игрушки характеризуются двумя параметрами — массой и красотой. Елка характеризуется тремя параметрами — максимальной массой игрушек, которую она может выдержать, красотой, а также максимальной перегрузкой в одну из сторон (максимальная разница между суммарной массой игрушек на левой и на правой стороне). Красота елки равна сумме красот всех висящих на ней игрушек. Так как дети хотят удивить Деда мороза, они хотят как можно красивее украсить ёлку, при этом она не должна упасть.

Вас просят написать программу, которая по заданным параметрам игрушек и ёлки определит максимально возможную красоту наряженной ёлки.

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

Во входном файле содержатся числа M K Δ — соответственно максимальная масса игрушек на ёлке, количество купленных игрушек и максимальное отклонение. За ними следуют K пар чисел vi ki соответственно вес и красота i-той игрушки.

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

В выходном файле должно содержаться единственное число - максимально возможная красота наряженной ёлки.

Ограничения

1 ≤ К, M ≤ 100 1 ≤ vi, ki ≤ 100 0 ≤ Δ ≤ 20

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 2 1
1 2
2 2
 
4

Задача D. Воздушный замок ≡

Автор:И. Туфанов, И. Олейников
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

Накануне нового года Дед Мороз занимается свим привычным делом: он строит воздушные замки. Пространство в котором Дед Мороз строит замки - это куб, который состоит из NxNxN маленьких кубиков. Каждый маленький кубик может быть занят облаком или не занят. Воздушный замок Деда Мороза - это прямоугольный паралеллепипед с целочисленными координатами, стороны которого параллельны осям координат. Кроме того, в пространсте есть M облаков. Дед Мороз не хочет, чтобы его замок задевал облака. Замок задевает облако, если они имеют общую клетку.

Помогите Деду Морозу постоить наибольший по объему замок.

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

Во входном файле содержатся числа N и M. За ними следуют M троек чисел - координаты облаков. Все координаты находятся в пределах между 1 и N включительно. Облака могут занимать одну и ту же клетку.

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

В выходном файле должно содержаться единственное число - объем самого просторного замка.

Ограничения

1 ≤ N ≤ 80 0 ≤ M ≤ 200000

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
2 1
1 1 2
 
4
2 
3 0

27
0.043s 0.005s 13