Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Пирамида (максимум)

Куча

Напишите программу, которая будет обрабатывать последовательность запросов таких видов:
 
CLEAR — сделать пирамиду пустой (если в пирамиде уже были какие-то элементы, удалить все). Действие происходит только с данными в памяти, на экран ничего не выводится.
 
ADD n — добавить в пирамиду число n. Действие происходит только с данными в памяти, на экран ничего не выводится.
 
EXTRACT — вынуть из пирамиды максимальное значение. Следует и изменить данные в памяти, и вывести на экран или найденное максимальное значение, или, если пирамида была пустой, слово "CANNOT" (большими буквами).
 
Входные данные
Во входных данных записано произвольную последовательность запросов CLEAR, ADD и EXTRACT — каждый в отдельной строке, согласно вышеописанному формату. Данные заканчиваются строкой "END!"
 
Суммарное количество всех запросов не превышает 200000.
 
Выходные данные
Для каждого запроса типа EXTRACT выведите на стандартный выход (экран) его результат (в отдельной строке).

Ввод Вывод
ADD 192168812
ADD 125
ADD 321
EXTRACT
EXTRACT
CLEAR
ADD 7
ADD 555
EXTRACT
EXTRACT
EXTRACT
END!
192168812
321
555
7
CANNOT
 

Поиск минимума с помощью приоритетной очереди

Куча

Дана последовательность чисел. Найти в ней наименьшее число.
 
Входные данные
Задано сначала число N (количество чисел в последовательности, 1<=N<=100000), а затем
N чисел.
 
Выходные данные
Выведите наименьшее число.

Ввод Вывод
7
4 2 5 -1 4 6 2
-1
 

Кот Гусь и случайная матрица

Куча Префиксные суммы(минимумы, ...)

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера n × m, содержащую числа от 0 до p − 1.
Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p − 1, независимо от остальных.
Ваша задача — найти прямоугольную подматрицу этой таблицы, в которой сумма делится на p.
Среди всех таких подматриц нужно найти ту, в которой сумма элементов максимальна.
Формально, вам необходимо найти такие 1 <= i1 <= i2 <= n, 1 <= j1 <= j2 <= m, что сумма ax,y по всем i1 <= x <= i2, j1 <= y <= j2 делится на p, и среди таких имеет максимальную сумму.

Формат входных данных
В первой строке входного файла расположено три целых числа n, m, p (1 <= n·m, p <= 1 000 000) — размерности матрицы и число, на которое должна делится сумма подматрицы.
В следующих n строках расположено по m целых чисел, j-е число в i-й строке равно ai,j (0 <= ai,j <= p − 1).
Гарантируется, что каждое число в a выбрано независимо случайно равновероятно от 0 до p−1.

Формат выходных данных
Выведите одно целое число — максимальную сумму прямоугольной подматрицы, в которой сумма делится на p.
Если таких нет, выведите 0.

Ввод Вывод
6 7 5
0 0 3 0 1 0 4
0 2 3 0 2 2 1
2 4 1 4 4 0 3
1 1 0 2 0 3 2
3 0 3 1 0 1 2
1 2 0 0 3 3 1
65