Back to School '16: Times Table

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

atarw has bought a number of times table sets in preparation for the difficult math in the upcoming school year. A times table set is a rectangular collection of columns, with respective heights of a times table which somehow helps atarw to visualize the math.

Times table set

Consider a 4 by 4 times table.

×1234
11234
22468
336912
4481216

These products are the heights of a set shown below.

1 2 3  4
2 4 6  8
3 6 9  12
4 8 12 16

He wants to stack them on top of each other M times within an originally empty C by R grid to form a cool 3D structure. When stacked, gravity takes effect on the individual columns causing them to drop down. The grid has a top-left corner at (1, 1) and a bottom right corner at (C, R). He may put more than one set at the same time. This effectively multiplies all the numbers (heights) in the times table.

2 4  6  8
4 8  12 16
6 12 18 24
8 16 24 32

After stacking these sets together, atarw wants to take a finger walk in the grid starting at position (c, r). He wants to take the longest finger walk on a strictly increasing path. Output the largest sum of a such a path. He may only finger walk to adjacent blocks (up, down, left, right).

Input Specification

The first line contains three space separated integers, C\ R\ M, the number of columns and rows on the grid and the number of times that atarw will place multiplication table sets.

The next M lines will contain 5 integers, x y w h n where (x, y) is the top left corner of the multiplication table set(s). w is the width and h is the height of the set(s). n is the number of sets to be inserted. It is guaranteed that the whole rectangle is within the grid.

Finally, the last line of input will contain c r, (c, r) is the starting position of the finger walk. It is guaranteed that the coordinates are within the grid.

Constraints

Subtask 1 [20%]

1 \le C, R, M \le 100
1 \le n \le 10

Subtask 2 [80%]

1 \le C, R \le 500
1 \le M \le 100\,000
1 \le n \le 100

Output Specification

A single integer, the largest sum of the longest finger walk possible modulo 1\,000\,000\,007.

Sample Input 1

5 4 3
1 1 3 3 1
3 3 3 2 2
2 4 2 1 4
2 1

Sample Output 1

35

Explanation for Sample Output 1

The structure is:

1 2 3  0 0
2 4 6  0 0
3 6 11 4 6
0 4 12 8 12

The longest path is: 2 \to 4 \to 6 \to 11 \to 12.

Sample Input 2

5 5 1
1 1 5 5 1
2 2

Sample Output 2

92

Comments


  • 1
    Epic1Online  commented on June 22, 2020, 6:18 p.m.

    I'm TLEing on subtask 2 and I'm not sure how to further optimize my code. I'm pretty sure that creating the structure is what takes the most time and needs to be quicker but I don't see how I can achieve that. Can anyone help me?


    • 1
      Kirito  commented on June 23, 2020, 3:07 a.m.

      I believe you can construct the structure in \mathcal O(Q + CR).