Chef and Maximum Sum Matrices
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Dreaming to manipulate the dimensions of spacetime one day, Chef satisfies himself with manipulating dimensions of abstract mathematical entities for now. Today, Chef has N lists consisting of integers. The ith list is represented as Li, and has size Si.
Chef has transformed the given lists of integers to form an N dimensional matrix M of size S1 × S2 × S3 × … × SN such that an entry j1, j2, j3, … , jN in the matrix M is obtained by taking product of given N integers L1[j1], L2[j2], L3[j3], ..., LN[jN], where Li[ji] denotes the jth integer in the ith list (1-based indexing).
To explore the mathematics of the matrix M deeply, Chef wants to compute the maximum submatrix sum in this matrix; but he is afraid of its high dimensionality. So, he asked you to help him. He asked you to compute two quantities, the maximum sub-matrix sum in the matrix M, and the number of submatrices having this maximum sum.
Since the second answer to this problem can be very large, output it modulo 109+7.
- First line of input contains a single integer T denoting the number of test cases.
- First line of each test case contains a single integer N denoting the number of lists of integers.
- Next N lines of each test case contains some space separated integers where integers in the ith line make up the ith list. Each list description has the following format.
- First integer Si in the ith line denotes the size of the ith list, and
- the next Si space separated integers are the elements in the list.
For each test case, output 2 space separated integers (second integer modulo 109 + 7) where the first integer denotes the maximum submatrix sum and the second denotes the number of such submatrices.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 9
- 1 ≤ Si ≤ 9
- -9 ≤ Li[j] ≤ 9
2 2 2 3 4 2 4 5 2 3 4 -5 4 3 -2 3 -2 Output 63 1 12 2
All the matrices with maximum sum are highlighted with coloured fencing.
|Tags||ad-hoc, cook66, easy-medium, greedy, ma5termind|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.