Plus
Pin


Problem description Progress
ID 30754. Finding the Minimum Using Priority Queue
Темы: heap   

Given a sequence of numbers. Find the smallest number in it.
 
Input
The number N is given first (the number of numbers in the sequence, 1<=N< ;=100000) and then
N numbers.
 
Output
Print the smallest number.

Enter Output
7
4 2 5 -1 4 6 2
-1
 

ID 30723. Pyramid (maximum)
Темы: heap   

Write a program that will process a sequence of queries like this:
 
CLEAR — make the pyramid empty (if there were already some elements in the pyramid, delete all). The action occurs only with the data in memory, nothing is displayed on the screen.
 
ADD n — add the number n to the pyramid. The action occurs only with the data in memory, nothing is displayed on the screen.
 
EXTRACT — take out the maximum value from the pyramid. You should both change the data in memory and display either the maximum value found, or, if the pyramid was empty, the word "CANNOT" (in capital letters).
 
Input
The input contains an arbitrary sequence of queries CLEAR, ADD and EXTRACT — each on a separate line, following the format described above. The data ends with the string "END!"
 
The total number of all requests does not exceed 200000.
 
Output
For each EXTRACT query, print its result to the standard output (screen) (on a separate line).

Enter Output
ADD 192168812
ADD 125
ADD 321
EXTRACT
EXTRACT
CLEAR
ADD7
ADD 555
EXTRACT
EXTRACT
EXTRACT
END!
192168812
321
555
7
CANNOT
 

ID 33256. Cat Goose and random matrix
Темы: heap    Prefix sums(minimums, ...)   

Cat Goose prepared for Nick Fury a rectangular table a of size \(n \cdot m\) containing numbers from 0 code> to p−1. Nick Fury immediately realized that each number in this table was chosen randomly with equal probability from 0 to p−1 , regardless of the others.

Your task — find a rectangular submatrix of this table, in which the sum is divisible by p. Among all such submatrices, you need to find the one in which the sum of the elements is maximum.

Formally, you need to find \(1 <= i_1 <= i_2 <= n\), \( 1 <= j_1 <= j_2 <= m\) that the sum of ax,y over all \(i_1 <= x <= i_2\), \(j_1 <= y <= j_2\) split on p, and among these has the maximum amount.

Input
The first line contains three integers n, m, p (\(1 <= n m, p <= 1,000,000\)) — dimensions of the matrix and the number by which the sum of the submatrix should be divided.
The following n lines contain m integers, the j-th number in the i-th line equals ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
It is guaranteed that each number in a is chosen independently at random, equiprobably from 0 to p−1.

Output
Print a single integer — the maximum sum of a rectangular submatrix where the sum is divisible by p. If there are none, print 0.

 

Examples
# Input Output
1
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