Back To School '16: Times Table

View as PDF

Submit solution

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

Author:
Problem types

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.

\displaystyle \begin{array}{c|cccc}
\times & 1 & 2 & 3 & 4 \\\hline
1 & 1 & 2 & 3 & 4 \\
2 & 2 & 4 & 6 & 8 \\
3 & 3 & 6 & 9 & 12 \\
4 & 4 & 8 & 12 & 16 \end{array}

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 such a path. He may only finger walk to adjacent blocks (up, down, left, right).

Input Specification

The first line will contain 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

There are no comments at the moment.