Khu Rừng 1

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Python 3 3.0s
Bộ nhớ:
Python 3 128M
Tác giả:
TCA_Khoa
Dạng bài
Điểm: 200 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

algorit oai hùng ngày nào nay đã trở thành bảo vệ của rừng AnLuuLand (có dạng hình chữ nhật kích thước \(M * N\)). Để đền đáp công lao to lớn của algorit, Chúa đất cho phép anh chọn một vùng đất hình chữ nhật có kích thước \(k * k\), có các cạnh song song với các bìa rừng, khai thác tài nguyên tại vùng đất này để lây kinh phí dựng nhà và lấy vợ.

Chúa đất chỉ cho phép anh khai thác cây trong đúng vùng đất mà anh ấy chọn. Biết giá trị của mỗi cây trong khu rừng AnLuuLand tại vị trí dòng \(i\) cột \(j\) là \(a_{ij}\) nguyên. Bạn hãy giúp algorit chọn một vùng đất có giá trị cao nhất mà vẫn thỏa mãn yêu cầu của Chúa đất.

Input

  • Dòng 1: Gồm 3 số \(m, n , k ( 1 ≤ k ≤ m, n ≤ 1000).\)

  • \(m\) dòng sau mỗi dòng \(n\) số nguyên là giá trị của mỗi cây trong khu rừng. Giá trị của mỗi cây là một số nguyên có trị tuyệt đối không quá \(10^9.\)

Output

  • Một số duy nhất là giá trị cao nhất mà algorit có thể nhận được.

Scoring

  • \(a_{ij} \leq |10^9|\)
  • Subtask \(1\) (\(20\%\) số điểm): \(n, m\) \(\leq 10\)
  • Subtask \(2\) (\(20\%\) số điểm): \(n, m\) \(\leq 60\)
  • Subtask \(3\) (\(20\%\) số điểm): \(n, m\) \(\leq 400\)
  • Subtask \(4\) (\(40\%\) số điểm):\(n, m\) \(\leq 1000\)

Example

Test 1

Input 
4 5 2
1 1 2 0 0
1 2 1 0 1
4 3 5 1 1
1 5 5 0 0
Output 
18
Note

Nguồn : VinhDinhCoder

Bình luận


  • -5
    Lê_Gia_Khánh    6:25 p.m. 27 Tháng 8, 2020

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


    • 1
      NgJaBach    1:13 p.m. 26 Tháng 8, 2020

      Fun fact: Chúa đất = Landlord = Điền chủ


      • 1
        NgJaBach    12:20 p.m. 26 Tháng 8, 2020

        Tổng cộng dồn rồi đấm ;-;


        • 1
          N7hoatt    6:03 p.m. 25 Tháng 8, 2020

          bâì này ez sao ít ai lm thế


          • -1
            N7hoatt    4:47 p.m. 23 Tháng 8, 2020

            lấy vợ luôn à

            2 phản hồi