| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 | 512 MB | 30 | 13 | 7 | 36.842% |
Luka stumbled upon a rectangular board of height $H$ and width $W$ divided into $W \times H$ unit squares. He quickly noticed that exactly $K$ of those unit squares are missing.
Interestingly enough, Luka just happens to have an infinite supply of L-shaped triominoes. Is it possible to tile the given board using these triominoes?
We consider the board to be correctly tiled if each unit square of the board is covered by a triomino square. Additionally, triominoes must not cover any of the missing squares, and should not overlap or stick out of the board. Of course, triominoes can be arbitrarily rotated by multiples of 90 degrees.
The first line contains three integers $W,ドル $H$ and $K$ (0ドル \le K \le W \cdot H$) from the task description.
The $i$-th of the next $K$ lines contains two integers $x_i$ (1ドル \le x_i \le W$) and $y_i$ (1ドル \le y_i \le H$), representing the coordinates of the $i$-th missing square. The given missing squares are pairwise distinct.
If Luka can successfully tile the given board, output "YES" in a single line. Otherwise, output "NO" in a single line.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | 2ドル \le W \le 13,ドル 2ドル \le H \le 1,000円,ドル $K \le 250$ |
| 2 | 7 | 2ドル \le W \le 13,ドル 2ドル \le H \le 10^9,ドル $K = 0$ |
| 3 | 11 | 2ドル \le W \le 3,ドル 2ドル \le H \le 10^9,ドル $K \le 250$ |
| 4 | 17 | 4ドル \le W \le 6,ドル 2ドル \le H \le 10^9,ドル $K \le 250$ |
| 5 | 35 | 7ドル \le W \le 13,ドル 2ドル \le H \le 10^9,ドル $K \le 250$ |
| 6 | 20 | 2ドル \le W \le 13,ドル 2ドル \le H \le 10^9,ドル $K \le 250$ |
4 3 3 1 1 1 3 4 3
YES
5 2 4 1 2 2 1 5 1 5 2
NO
Luka cannot place a valid triomino which tiles square (1, 1).
2 3 0
YES