17629번 - T - Covering 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 7 | 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:
- The number of T-tetrominoes has to be the same as the number of special cells. For each T-tetromino, its center cell has to lie on some special cell.
- No pair of T-tetrominoes may overlap.
- All T-tetrominoes have to completely lie on the grid.
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 ≤ mn ≤ 106
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 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. |
예제 입력 1
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
예제 출력 1
67
To achieve the maximum sum, Nika may place the tetrominoes as follows:
- ┤ on the cell (1, 1);
- ├ on the cell (2, 2);
- ┴ on the cell (3, 4).
예제 입력 2
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
예제 출력 2
No
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호