| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 16 | 1 | 1 | 100.000% |
If you have ever played Tetris, you might know that one of the figures looks as follows:
We will call this figure a T-tetromino; a tetromino is just a fancy word for a connected geometric figure composed of four cells. The cell marked with will × be called the center cell.
Manca draws a rectangular grid with m rows and n columns and writes a number into each cell. The rows of the table are numbered from 0 to m-1 and the columns are numbered from 0 to n-1. She also marks some cells as special, e.g., by painting them red. After that, she asks Nika, a friend of hers, to place T-tetrominoes on the grid in such a way that the following conditions are met:
Note that there are four possible orientations of each T-tetromino (┬, ┴, ├, and ┤).
If the conditions cannot be satisfied, Nika should answer No; if they can, she has to find such a placement of T-tetrominoes that the sum of the numbers in the cells covered by the T-tetrominoes is maximum possible. In this case, she has to tell Manca the maximum sum.
Write a program to help Nika solve the riddle.
Each line contains a sequence of integers separated by a single space.
The first line of the input contains the integers m and n. Each of the following m lines contains n integers from the interval [0, 1000]. The j-th integer in the i-th line represents the number written in the j-th cell of the i-th row of the grid. The next line contains an integer k ∈ {1, ..., mn}. This line is followed by k more lines, each of which consists of integers ri ∈ {0, ..., m-1} and ci ∈ {0, ..., n-1}, which represent the position (the row index and column index, respectively) of the i-th special cell. The list of special cells does not contain any duplicates.
Print the maximum possible sum of the numbers in the cells covered by the T-tetrominoes, or No if no valid placement of T-tetrominoes exists.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | k ≤ 1000; for each pair of distinct special cells i and j, we have |ri - rj| > 2 or |ci - cj| > 2. |
| 2 | 10 | k ≤ 1000; for each pair of distinct special cells i and j, it holds that if |ri - rj| ≤ 2 and |ci - cj| ≤ 2, then (ri, ci) and (rj, cj) are adjacent by side, or more formally the following statement is true (|ri - rj| = 1 and |ci - cj| = 0) or (|ri - rj| = 0 and |ci - cj| = 1). |
| 3 | 10 | k ≤ 1000; for each pair of distinct special cells i and j, it holds that if |ri - rj| ≤ 2 and |ci - cj| ≤ 2, then |ri - rj| ≤ 1 and |ci - cj| ≤ 1. |
| 4 | 10 | k ≤ 1000; all special cells lie in the same row. |
| 5 | 15 | k ≤ 10. |
| 6 | 20 | k ≤ 1000. |
| 7 | 30 | no additional constraints. |
5 6 7 3 8 1 0 9 4 6 2 5 8 3 1 9 7 3 9 5 2 6 8 4 5 7 3 8 2 7 3 6 3 1 1 2 2 3 4
67
To achieve the maximum sum, Nika may place the tetrominoes as follows:
5 6 7 3 8 1 0 9 4 6 2 5 8 3 1 9 7 3 9 5 2 6 8 4 5 7 3 8 2 7 3 6 3 1 1 2 2 3 3
No