Thẻ

Đề bài

http://laptrinh.ntu.edu.vn/Problem/Details/76

Trên một vùng đất hình vuông các nhà địa chất phát hiện ra có trữ lượng vàng khá lớn. Để tiện việc khai thác, người ta chia vùng đất thành các lô nhỏ, tổng cộng có n x n lô (n dòng, n cột). Ta đánh số các dòng từ 1 đến n theo chiều từ trên xuống dưới, các cột từ 1 đến n theo chiều từ trái qua phải. Tại lô đất ở dòng i cột j, người ta đo được trữ lượng vàng là ai j. Tuy nhiên, do giới hạn về kỹ thuật chỉ cho phép khai thác trong một diện tích nhỏ gồm k x k lô mà thôi. Bạn hãy giúp chọn hình vuông k x k lô nào cần khai thác để có sản lượng vàng là lớn nhất.

Dữ liệu nhập:

– Dòng thứ nhất là 2 số nguyên n, k (1 ≤ k ≤ n ≤ 1000)

– Trong n dòng tiếp theo, mỗi dòng gồm n số ai j xác định trữ lượng tại lô dòng i cột j (0 ≤ ai j ≤ 1000)

Dữ liệu xuất:

– Là một số nguyên duy nhất xác định sản lượng vàng lớn nhất khai thác được.

Ví dụ

  • input
    4 3
    1 9 1 1
    9 9 9 9
    1 9 9 9
    1 9 9 14
    output
    86

Giải thích: khai thác trong các lô đánh dấu đỏ

1 9 1 1
9 9 9 9
1 9 9 9
1 9 9 14

Họ làm như sau:
Gọi T[i,j] sẽ là tổng của tất cả a[x,y] với x<i, và y<j.

Muốn tính tổng của khu vực x, ta chỉ cần trừ đi phần phía trên và phần phía trong của nó (cộng lại phần bù vì nó bị trừ 2 lần) là ok!

sourcecode

daovang

Advertisements