PVHOI 2.0 - Bài 1- Chất lượng cuộc sống

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 2.5s
Memory limit: 1G

Author:
Problem source:
PVHOI 2.0
Problem type
Allowed languages
C, C++, Java, Pascal, Python

Thành phố Nồi Hạ có phân bổ dân cư hết sức đặc biệt: Thành phố có ~r \cdot c~ khu dân cư đựoc xếp dưới dạng lưới hình chữ nhật gồm ~r~ hàng và ~c~ cột. Các hàng được đánh số từ ~1~ đến ~r~, các cột được đánh số từ ~1~ đến ~c~. Khu dân cư nằm trên giao của hàng ~i~ và cột ~j~ được kí hiệu là ~(i, j)~.

Trong đợt khảo sát vừa qua, lãnh đạo thành phố đã đi từng ngõ, gõ từng nhà để thu thập thông tin về chất lượng cuộc sống ở các khu dân cư. Tiếp đó, họ xếp hạng các khu dân cư bằng các con số phân biệt từ ~1~ đến ~r \cdot c~. Khu dân cư xếp hạng ~1~ có chất lượng cuộc sống tốt nhất. Khu dân cư xếp hạng ~r \cdot c~ có chất lượng tệ nhất. Khu dân cư được xếp hạng càng nhỏ thì chất lượng sống càng cao. Theo kết quả, khu dân cư ~(i, j)~ được xếp hạng ~p_{i, j}~.

Từ kết quả xếp hạng, thành phố sẽ chọn ra một khu vực để tăng cường đầu tư nhằm nâng cao chất lượng cuộc sống ở đây. Thành phố quyết định rằng các khu dân cư được nâng cấp sẽ nằm trong một hình chữ nhật con có kích thước ~h \cdot w~ (gồm ~h~ hàng và ~w~ cột), với ~h~ và ~w~ là các số lẻ. Lãnh đạo thành phố muốn chọn những nơi chất lượng sống còn thấp để ưu tiên cải tạo, nhưng họ cần đưa ra một tiêu chí đánh giá chung cho một vùng hình chữ nhật kích thước ~h \cdot w~. Theo đó, "mức sống tiêu biểu" của một khu vực là trung vị của thứ hạng chất lượng cuộc sống của các khu dân cư bên trong đó. (xem phần dưới để biết định nghĩa về trung vị)

Khu vực được chọn để đầu tư phải có "mức sống tiêu biểu" lớn nhất (vì thứ hạng càng lớn thì chất lượng cuộc sống càng thấp) trong các khu vực có thể chọn. Bạn hãy giúp họ tìm ra "mức sống tiêu biểu" lớn nhất này nhé.

Giá trị trung vị của một dãy số ~(a_1, a_2, \ldots, a_n)~ (với ~n~ là số lẻ) là giá trị thứ ~\frac{n+1}{2}~ (ở vị trí chính giữa) của dãy số sau khi dãy đã được sắp xếp theo thứ tự tăng dần. Ví dụ, trung vị của dãy ~(22, 7, 97)~ là ~22~ (do dãy sau khi sắp xếp trở thành ~(7, 22, 97)~; trung vị của dãy ~(2, 2, 7, 1, 9, 9, 7)~ là ~7~ (do dãy sau khi sắp xếp trở thành ~(1, 2, 2, 7, 7, 9, 9)~.

Input

Dòng đầu tiên chứa bốn số nguyên ~r~, ~c~, ~h~, ~w~ ~(1 \leq h \leq r \leq 3000, 1 \leq w \leq c \leq 3000)~, lần lượt là kích thước của thành phố Nồi Hạ và kích thước vùng được chọn để nâng cao chất lượng cuộc sống. Dữ liệu vào đảm bảo ~h~ và ~w~ là các số lẻ.

Trong ~r~ dòng còn lại, dòng thứ ~i~ chứa ~c~ số nguyên ~p_{i, 1}, p_{i, 2}, \ldots, p_{i, c}~ ~(1 \leq p_{i, j} \leq r \cdot c)~, trong đó ~p_{i, j}~ là thứ hạng chất lượng cuộc sống của khu ~(i, j)~. Dữ liệu vào đảm bảo ~r \cdot c~ số này là đôi một phân biệt.

Output

In ra một số nguyên duy nhất là "mức sống tiêu biểu" lớn nhất của một khu vực có dạng hình chữ nhật kích thước ~h \cdot w~.

Subtasks

Bộ test của bài được chia làm các subtask như sau:

  • Subtask ~1~ (~3~ test): ~h = w = 1~
  • Subtask ~2~ (~3~ test): ~h = r~ và ~w = c~
  • Subtask ~3~ (~15~ test): ~r, c \leq 30~
  • Subtask ~4~ (~14~ test): ~r, c \leq 100~
  • Subtask ~5~ (~6~ test): ~r, c \leq 300~
  • Subtask ~6~ (~6~ test): ~r, c \leq 1000~
  • Subtask ~7~ (~4~ test): Không có ràng buộc gì thêm.

Ví dụ

Input

5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15

Output

20

Giải thích

Trong ví dụ ở trên, lãnh đạo thành phố nên chọn hình chữ nhật kích thước ~3 \cdot 3~ ở góc trái dưới làm khu vực được nâng cấp. Thứ hạng của các khu dân cư bên trong khu vực này lần lựot là ~4, 23, 20, 24, 21, 19, 6, 22, 8~ (được sắp xếp theo thứ tự tăng dần là ~4, 6, 8, 19, 20, 21, 22, 23, 24~). Nhu vậy, ``mức sống tiêu biểu'' của khu vực này là ~20~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.