Matrix Maximum Sum
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Devu and Churu love to play with numbers. Today, each of them has an 1 - based array consisting of N positive integers. Devu named his array as A while Churu called his array B. They have decided to construct a matrix C of size N × N using given arrays A and B where an entry Ci,j in the matrix is given by following expression.
where Ci,j denotes the value of the jth cell in the ith row of matrix C, Ai denotes the ith element of the array A and Bj denotes the jth element of the array B.
For example, consider the following arrays A and B each containing 3 elements.
A = [4, 1, 9] B = [3, 4, 1] Constructed matrix C will look like: [20, 30, 20], C = [12, 18, 12], [48, 72, 48],
Then, for a given K, they will create a list LK of all sub-matrices of size K x K from the constructed matrix C and compute the following expression over the created list LK.
where max( X ) denotes the maximum element present in the matrix X.
For example, consider the above matrix C and K = 2. Here, LK contains following 4 sub-matrices of size 2 x 2.
[20, 30] [30, 20] [12, 18] [18, 12] [12, 18] [18, 12] [48, 72] [72, 48] M1 = 30 M2 = 30 M3 = 72 M4 = 72
Therefore, for K = 2, S = M1 + M2 + M3 + M4 = (30 + 30 + 72 + 72) % (109 + 7) = 204.
Devu and Churu like the task very much and decided to compute the above expression for all possible values of K such that 1 ≤ K ≤ N but suddenly their mom called them for some urgent work and they had to leave the task in between. Can you help them completing this task?
The first line of input contains a single integer N denoting the size of both arrays A and B. Second line of input contains N space-separated integers denoting the array A. Third line of input also contains N space separated integers, denoting the array B.
Output N space-separated integers, where the ith integer in the output denotes the required answer considering all sub-matrices of size i x i.
- 1 ≤ N ≤ 105
- 1 ≤ Ai, Bj ≤ 109
- 1 ≤ N ≤ 104 : ( 40 pts )
- 1 ≤ N ≤ 105 : ( 60 pts )
Input 3 4 1 9 3 4 1 Output 280 204 72
|Tags||easy-medium, feb16, ma5termind|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.