English · Original
Chinese · Translation
Formal · Original
Recently Luba bought a monitor. Monitor is a rectangular matrix of size _n_ × _m_. But then she started to notice that some pixels cease to work properly. Luba thinks that the monitor will become broken the first moment when it contains a square _k_ × _k_ consisting entirely of broken pixels. She knows that _q_ pixels are already broken, and for each of them she knows the moment when it stopped working. Help Luba to determine when the monitor became broken (or tell that it's still not broken even after all _q_ pixels stopped working).
## Input
The first line contains four integer numbers _n_, _m_, _k_, _q_ (1 ≤ _n_, _m_ ≤ 500, 1 ≤ _k_ ≤ _min_(_n_, _m_), 0 ≤ _q_ ≤ _n_·_m_) — the length and width of the monitor, the size of a rectangle such that the monitor is broken if there is a broken rectangle with this size, and the number of broken pixels.
Each of next _q_ lines contain three integer numbers _x__i_, _y__i_, _t__i_ (1 ≤ _x__i_ ≤ _n_, 1 ≤ _y__i_ ≤ _m_, 0 ≤ _t_ ≤ 109) — coordinates of _i_\-th broken pixel (its row and column in matrix) and the moment it stopped working. Each pixel is listed at most once.
We consider that pixel is already broken at moment _t__i_.
## Output
Print one number — the minimum moment the monitor became broken, or "-1" if it's still not broken after these _q_ pixels stopped working.
[samples]
最近，Luba 买了一台显示器。这台显示器是一个大小为 $n × m$ 的矩形矩阵。但她发现有些像素点开始无法正常工作。Luba 认为，当显示器中出现一个由完全损坏像素组成的 $k × k$ 正方形时，显示器就会变得损坏。她知道已经有 $q$ 个像素点损坏，并且对于每个像素点，她都知道它停止工作的时刻。请帮助 Luba 确定显示器何时变得损坏（如果在所有 $q$ 个像素点都损坏后仍未损坏，请说明这一点）。
第一行包含四个整数 $n, m, k, q$ ($1 ≤ n, m ≤ 500$, $1 ≤ k ≤ \min(n, m)$, $0 ≤ q ≤ n·m$) —— 分别表示显示器的长、宽、导致显示器损坏的正方形尺寸，以及已损坏像素的数量。
接下来的 $q$ 行，每行包含三个整数 $x_i, y_i, t_i$ ($1 ≤ x_i ≤ n$, $1 ≤ y_i ≤ m$, $0 ≤ t_i ≤ 10^9$) —— 第 $i$ 个损坏像素的坐标（矩阵中的行和列）以及它停止工作的时刻。每个像素最多只列出一次。
我们认为像素在时刻 $t_i$ 时已经损坏。
请输出一个数字 —— 显示器首次变得损坏的最小时刻，或在所有 $q$ 个像素点损坏后仍未损坏时输出 "-1"。
## Input
第一行包含四个整数 $n, m, k, q$ ($1 ≤ n, m ≤ 500$, $1 ≤ k ≤ \min(n, m)$, $0 ≤ q ≤ n·m$) —— 分别表示显示器的长、宽、导致显示器损坏的正方形尺寸，以及已损坏像素的数量。接下来的 $q$ 行，每行包含三个整数 $x_i, y_i, t_i$ ($1 ≤ x_i ≤ n$, $1 ≤ y_i ≤ m$, $0 ≤ t_i ≤ 10^9$) —— 第 $i$ 个损坏像素的坐标（矩阵中的行和列）以及它停止工作的时刻。每个像素最多只列出一次。我们认为像素在时刻 $t_i$ 时已经损坏。
## Output
请输出一个数字 —— 显示器首次变得损坏的最小时刻，或在所有 $q$ 个像素点损坏后仍未损坏时输出 "-1"。
[samples]
Given:
- A binary matrix $ A \in \{0,1\}^{n \times m} $, where $ A_{i,j} = 1 $ if pixel at position $ (i,j) $ is broken, $ 0 $ otherwise.
- A set of $ q $ broken pixels, each with coordinates $ (x_i, y_i) $ and failure time $ t_i $, for $ i = 1, \dots, q $.
- A threshold $ k \in \mathbb{Z}^+ $, $ k \leq \min(n, m) $.
Define:
- For any time $ T \geq 0 $, let $ A^T \in \{0,1\}^{n \times m} $ be the matrix where $ A^T_{i,j} = 1 $ if and only if there exists a broken pixel at $ (i,j) $ with $ t_i \leq T $, otherwise $ 0 $.
Define the condition:
- The monitor is **broken** at time $ T $ if there exists a $ k \times k $ contiguous submatrix in $ A^T $ consisting entirely of 1s.
Objective:
- Find the **minimum** time $ T^* $ such that $ A^{T^*} $ contains a $ k \times k $ all-ones submatrix.
- If no such $ T $ exists among all $ t_i $, return $ -1 $.
Formally:
Let $ \mathcal{T} = \{ t_1, t_2, \dots, t_q \} \cup \{0\} $ (sorted in increasing order).
Find the smallest $ T \in \mathcal{T} $ such that
$$
\exists \, (i,j) \in \{1, \dots, n-k+1\} \times \{1, \dots, m-k+1\} \quad \text{with} \quad \forall \, (a,b) \in [i, i+k-1] \times [j, j+k-1], \; A^T_{a,b} = 1.
$$
If no such $ T $ exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "D. Monitor",
"description": {
"content": "Recently Luba bought a monitor. Monitor is a rectangular matrix of size _n_ × _m_. But then she started to notice that some pixels cease to work properly. Luba thinks that the monitor will become brok",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF846D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Recently Luba bought a monitor. Monitor is a rectangular matrix of size _n_ × _m_. But then she started to notice that some pixels cease to work properly. Luba thinks that the monitor will become brok...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "最近，Luba 买了一台显示器。这台显示器是一个大小为 $n × m$ 的矩形矩阵。但她发现有些像素点开始无法正常工作。Luba 认为，当显示器中出现一个由完全损坏像素组成的 $k × k$ 正方形时，显示器就会变得损坏。她知道已经有 $q$ 个像素点损坏，并且对于每个像素点，她都知道它停止工作的时刻。请帮助 Luba 确定显示器何时变得损坏（如果在所有 $q$ 个像素点都损坏后仍未损坏，请说明这...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Given:\n- A binary matrix $ A \\in \\{0,1\\}^{n \\times m} $, where $ A_{i,j} = 1 $ if pixel at position $ (i,j) $ is broken, $ 0 $ otherwise.\n- A set of $ q $ broken pixels, each with coordinates $ (x_i, ...",
"is_translate": false,
"language": "Formal"
}
]
}