VM 09 Bài 08 - Giá trị chiếc quạt mo

Xem dạng PDF

Gửi bài giải


Điểm: 0,98 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VNOI Marathon 2009Round 3Problem Setter: Ðỗ Ðức Ðông
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Phú ông có một mảnh đất hình chữ nhật được chia thành lưới ô vuông gồm ~M~ hàng và ~N~ cột. Các hàng của lưới được đánh số từ trên xuống dưới bắt đầu từ ~1~, còn các cột đánh số từ trái sang phải, bắt đầu từ ~1~. Ô nằm giao của hàng ~i~ và cột ~j~ là ô đất ~i, j~ ~(i = 1 \dots M, j = 1 \dots N)~ có độ cao là ~h_{ij}~. Phú ông đã đưa ra đề nghị đổi chiếc quạt mo lấy đất như sau:

  • Bờm được quyền chọn ~2~ mảnh đất con (một mảnh để làm nhà, một mảnh để trồng rau), hai mảnh đều có dạng hình chữ nhật và chứa nguyên các ô.
  • Mỗi mảnh đất có độ chênh lệch không quá ~K~, nghĩa là hiệu độ cao của ô có độ cao nhất với ô có độ cao thấp nhất không vượt quá ~K~.
  • Hai mảnh đất được chọn không giao nhau nhưng có thể tiếp xúc nhau.
  • Hãy giúp Bờm chọn được hai mảnh đất thỏa mãn điều kiện của phú ông và có tổng diện tích là lớn nhất.

Input

  • Dòng đầu là ~3~ số ~M, N~ và ~K~ ~(M, N \leq 300)~.
  • ~M~ dòng sau, mỗi dòng gồm ~N~ số nguyên ~h_{ij}~ mô tả mảnh đất ~(K, |h_{ij}|<10^{9})~.

Output

Một số là tổng diện tích lớn nhất tìm được.

Giới hạn

Có ~50\%~ số test với ~m,n\leq 50~.

Sample Input

3 4 0
1 2 3 1
1 9 9 1
2 2 2 2

Sample Output

6

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -1
    buu_ske155  đã bình luận lúc 15, Tháng 11, 2023, 4:17

    ez gg


  • -2
    neptune_170_nt  đã bình luận lúc 29, Tháng 1, 2023, 5:44 chỉnh sửa

    Ý tưởng bài này

    Duyệt trâu kết hợp Monotonic Queue


  • -6
    HoangVu_cva  đã bình luận lúc 23, Tháng 9, 2021, 16:49

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.