Bò Lười (Silver)

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một lưới $N \times N$ ô, mỗi ô $(r, c)$ chứa $G (r, c)$ đơn vị cỏ. Một con bò chọn một ô để đứng và có thể di chuyển tối đa $K$ bước (mỗi bước sang ô kề cạnh: trên, dưới, trái, phải). Con bò ăn tất cả cỏ ở các ô mà nó có thể đến được trong $K$ bước (tức các ô có khoảng cách Manhattan $\leq K$ ).

Hãy tìm vị trí đứng tối ưu để con bò ăn được nhiều cỏ nhất.

Dữ liệu vào

Dòng đầu tiên: hai số nguyên $N$ và $K$ .
$N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên biểu diễn lượng cỏ trên mỗi ô.

Dữ liệu ra

Một số nguyên duy nhất — tổng lượng cỏ lớn nhất có thể ăn được.

Ràng buộc

$1 \leq N \leq 400$
$0 \leq K \leq 2 N$
$0 \leq G (r, c) \leq 1000$

Ví dụ

Input	Output	Giải thích
5 2 50 5 25 6 17 14 3 2 7 21 99 10 1 2 80 8 7 5 23 11 10 0 78 1 9	342	Đứng ở ô $(3, 3)$ , con bò có thể đến tất cả các ô có khoảng cách Manhattan $\leq 2$ : tổng cỏ $= 25 + 3 + 2 + 7 + 99 + 10 + 1 + 2 + 80 + 7 + 5 + 23 + 78 = 342$ .

Bình luận

Không có bình luận tại thời điểm này.