#1263. MEDIAN - Trung vị

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: Bài tập Đội Bắc Giang ôn thầy Đỗ Đức Đông - Tháng 10/2017

Cho bảng số nguyên không âm kích thước 𝑚 × 𝑛 và hai số lẻ 𝑟, 𝑐 . Hãy tìm bảng con kích thước 𝑟 × c để giá trị trung vị của các số trong bảng là nhỏ nhất.

Dữ liệu vào:

  • Dòng đầu chứa bốn số nguyên 𝑚, 𝑛, 𝑟, 𝑐 ;
  • Tiếp theo là 𝑚 dòng, mỗi dòng chứa 𝑛 số nguyên không âm mô tả bảng số (các số không vượt quá 10^9 ).

Dữ liệu ra:

  • Gồm một số là trung vị nhỏ nhất tìm được.

Ví dụ:

Dữ liệu vào:
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
Dữ liệu ra:
9

Giới hạn:

  • Subtask \#1: 𝑚, 𝑛 ≤ 30 ;
  • Subtask \#2: 𝑚, 𝑛 ≤100 ;
  • Subtask \#3: 𝑚, 𝑛 ≤300 ;
  • Subtask \#4: 𝑚, 𝑛 ≤1000 .