P15406 [NOISG 2026 Prelim] Skyscrapers (No testdata yet)

The newly built residential area in City W is an $n \times n$ grid, and one skyscraper is built in each cell. It is known that there are $cnt_i$ skyscrapers with height $h_i$. Definition: The lighting parameter of a building is the number of directions among the four directions (up, down, left, right) that satisfy “in that direction, there is no building taller than it”. Each building is required to have a lighting parameter $\ge k$. Determine whether there exists a placement that satisfies the requirement.

- The first line: two integers $n, k$, representing the side length of the grid and the lighting requirement. $(1 \le n \le 1000, 0 \le k \le 4)$. - The second line: one integer $m$, the number of skyscraper types. $(1 \le m \le 10^4)$. - The next $m$ lines: each line contains two integers $h_i, cnt_i$, meaning there are $cnt_i$ skyscrapers of height $h_i$. $(1 \le h_i \le 10^9, 1 \le cnt_i \le n^2)$. It is guaranteed that $\sum cnt_i = n^2$, and all $h_i$ are pairwise distinct.

If there exists a placement such that all skyscrapers have a lighting parameter $\ge k$, output YES; otherwise, output NO.

### Constraints - $1 \le n \le 1000$. - $0 \le k \le 4$. - $1 \le m \le 10^4$. - $1 \le h_i \le 10^9$. - $1 \le cnt_i \le n^2$. - $\sum cnt_i = n^2$. - All $h_i$ are distinct. ### Subtasks |Subtask ID|Property|Score| |:-:|:-:|:-:| |1|$k = 0$|1| |2|$k = 1$|2| |3|$k = 2$|3| |4|$k = 4$|4| |5|$n \le 4$|10| |6|$m \le 10$|30| |7|$h$ and $cnt$ are generated uniformly at random within the limits (10 sets)|20| |8|No special limits|30| Translated by ChatGPT 5