TopCoder

Thumb 1800
weyryafjnm;
ちょっと天井見てくるわ。。。

User's AC Ratio

93.8% (15/16)

Submission's AC Ratio

52.9% (27/51)

Tags

Description

在競賽圈有個潛規則,你如果想要變強,你就要去吃碗拉麵,而且你吃的拉麵越好吃,你就會變得越強。
在天龍國裡,有許多家麵店,而你手上有一張 $(n \times m)$ 的拉麵店地圖。
其中第 $i$ 行第 $j$ 列的個子就是 $w_{i,j}$
當 $w_{i,j} > 0$ 時,代表在 $(i,j)$ 上有一間美味程度為 $w_{i,j}$ 的拉麵店。
當 $w_{i,j} = 0$ 時,代表在 $(i,j)$ 上面有一位競賽選手
當 $w_{i,j} < 0$ 時,代表在 $(i,j)$ 上面什麼都沒有

而且對於兩兩不同的麵店,他們的美味程度不會重複。

有許多競賽選手想要去吃拉麵。
每個人都想吃最好吃的拉麵,
可是如果大家都擠在同一間拉麵店的話,就要等很久。

聰明的你想到了一個辦法。
分別 規定所有人都只能前往和它距離 $K$ 以內的拉麵店。
也就是說,你不需要給所有人相同的限制,如果你喜歡蕭800 那你就給他限制 $K$ 大一點,如果你覺得蛋餅該少吃拉麵,你就限制他 $K$ 小一點。

其中兩個座標 $(x_1, y_1), (x_2, y_2)$ 的距離定為 $\max(|x_1-x_2|, |y_1-y_2|)$

在這樣的狀況下,所有人都會前往他可以去的拉麵店中,做出最美味拉麵的店。

如此一來,就不會所有人都擠在同一間拉麵店裡了

現在,你想知道如果你好好限制大家,最多能有幾間拉麵店有人光顧

Input Format

第一行有兩個正整數 $ n, m (n \times m \leq 300) $
接下來 $n$ 行,每行有 $ m $個整數
其中第 $ i $ 行第 $j$ 個代表 $w_{ij}, (-1 \leq w_{ij} \leq n \times m)$

Output Format

輸出一個整數代表答案

Sample Input

3 5
-1 0 3 -1 -1
-1 2 -1 0 -1
0 1 -1 -1 4

Sample Output

3

Hints

對於範測一,假如我們讓限制為 (1, 2) : 2, (2, 4) : 2, (3, 1) : 1 的話
在 (1, 2) 上的選手會到 (1, 3) 的拉麵店
在 (2, 4) 上的選手會到 (3, 5) 的拉麵店
在 (3, 1) 上的選手會到 (2, 2) 的拉麵店

Problem Source

by kevin_zhang

Subtasks

No. Testdata Range Constraints Score
1 0~19 $ n \cdot m \leq 10 $ 10
2 0~49 $ n = 1 $ 30
3 0~99 no additional limits 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3
1 1000 65536 65536 1 2 3
2 1000 65536 65536 1 2 3
3 1000 65536 65536 1 2 3
4 1000 65536 65536 1 2 3
5 1000 65536 65536 1 2 3
6 1000 65536 65536 1 2 3
7 1000 65536 65536 1 2 3
8 1000 65536 65536 1 2 3
9 1000 65536 65536 1 2 3
10 1000 65536 65536 1 2 3
11 1000 65536 65536 1 2 3
12 1000 65536 65536 1 2 3
13 1000 65536 65536 1 2 3
14 1000 65536 65536 1 2 3
15 1000 65536 65536 1 2 3
16 1000 65536 65536 1 2 3
17 1000 65536 65536 1 2 3
18 1000 65536 65536 1 2 3
19 1000 65536 65536 1 2 3
20 1000 65536 65536 2 3
21 1000 65536 65536 2 3
22 1000 65536 65536 2 3
23 1000 65536 65536 2 3
24 1000 65536 65536 2 3
25 1000 65536 65536 2 3
26 1000 65536 65536 2 3
27 1000 65536 65536 2 3
28 1000 65536 65536 2 3
29 1000 65536 65536 2 3
30 1000 65536 65536 2 3
31 1000 65536 65536 2 3
32 1000 65536 65536 2 3
33 1000 65536 65536 2 3
34 1000 65536 65536 2 3
35 1000 65536 65536 2 3
36 1000 65536 65536 2 3
37 1000 65536 65536 2 3
38 1000 65536 65536 2 3
39 1000 65536 65536 2 3
40 1000 65536 65536 2 3
41 1000 65536 65536 2 3
42 1000 65536 65536 2 3
43 1000 65536 65536 2 3
44 1000 65536 65536 2 3
45 1000 65536 65536 2 3
46 1000 65536 65536 2 3
47 1000 65536 65536 2 3
48 1000 65536 65536 2 3
49 1000 65536 65536 2 3
50 1000 65536 65536 3
51 1000 65536 65536 3
52 1000 65536 65536 3
53 1000 65536 65536 3
54 1000 65536 65536 3
55 1000 65536 65536 3
56 1000 65536 65536 3
57 1000 65536 65536 3
58 1000 65536 65536 3
59 1000 65536 65536 3
60 1000 65536 65536 3
61 1000 65536 65536 3
62 1000 65536 65536 3
63 1000 65536 65536 3
64 1000 65536 65536 3
65 1000 65536 65536 3
66 1000 65536 65536 3
67 1000 65536 65536 3
68 1000 65536 65536 3
69 1000 65536 65536 3
70 1000 65536 65536 3
71 1000 65536 65536 3
72 1000 65536 65536 3
73 1000 65536 65536 3
74 1000 65536 65536 3
75 1000 65536 65536 3
76 1000 65536 65536 3
77 1000 65536 65536 3
78 1000 65536 65536 3
79 1000 65536 65536 3
80 1000 65536 65536 3
81 1000 65536 65536 3
82 1000 65536 65536 3
83 1000 65536 65536 3
84 1000 65536 65536 3
85 1000 65536 65536 3
86 1000 65536 65536 3
87 1000 65536 65536 3
88 1000 65536 65536 3
89 1000 65536 65536 3
90 1000 65536 65536 3
91 1000 65536 65536 3
92 1000 65536 65536 3
93 1000 65536 65536 3
94 1000 65536 65536 3
95 1000 65536 65536 3
96 1000 65536 65536 3
97 1000 65536 65536 3
98 1000 65536 65536 3
99 1000 65536 65536 3