Oranges

Xem PDF



Thời gian:
Python 3 5.0s
Bộ nhớ:
Python 3 256M

Tác giả:
Dạng bài
Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Minh là người thắng cuộc trong cuộc thi “Hái hoa quả” và được nhận một phần thưởng do nhà vườn ĐÔRA tài trợ đó là những trái cam tươi ngon. Các phần thưởng được bố trí trên một bảng hình vuông có kích thước \(n \times n\) có dạng một lưới ô vuông kích thước đơn vị. Các dòng của bảng được đánh số từ \(1\) đến \(n\), từ trên xuống dưới và các ô của bảng được đánh số từ \(1\) đến \(n\), từ trái sang phải. Ô nằm trên giao của dòng \(i\) và cột \(j\) gọi là ô \((i,j)\) và trên đó có một món quà có giá trị là \(a_{ij}\) tương ứng với số trái cam \((1 \leq i,j \leq n)\).

Để nhận được phần thưởng, Minh được phép chọn một hình vuông kích thước \(k \times k\) chiếm chọn một ô của bảng và nhận hết tất cả trái cam nằm trong các ô của hình vuông đó.

Yêu cầu: Hãy xác định tổng số cam lớn nhất mà Minh có thể nhận được?

Input

  • Dòng thứ nhất chứa 2 số nguyên dương \(n\)\(k\).
  • Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa \(n\) số nguyên dương, số thứ \(j\)\(a_{ij}(a_{ij}<1000)\)

Output

  • Gồm 1 số duy nhất là tổng số cam lớn nhất mà Minh nhận được.

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): \(n<50\)
  • Subtask \(2\) (\(75\%\) số điểm): \(n<1000\)

Example

Test 1

Input
4 3 
1 9 1 1 
9 9 9 9 
1 9 9 9 
1 9 9 14 
Output
86

Bình luận


  • 3
    minhtuanitk20 6:40 p.m. 20 Tháng 1, 2022

    bài này mọi người có thể hiểu là prefix sum trên mảng 2D ứng dụng kiến thức bao lồi


    • 2
      minhtuanitk20 11:34 a.m. 20 Tháng 9, 2021

      quy hoạch như qbmax


      • -1
        sunflower 9:36 a.m. 19 Tháng 9, 2021

        bài này dùng ứng dụng frefix-sum vẫn AC nha mn


        • -6
          rukashii 6:03 p.m. 18 Tháng 9, 2021

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

          1 phản hồi