Chụp Ảnh

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Farmer John muốn chụp ảnh các con bò trong lưới $N \times N$ . Máy ảnh chụp được vùng vuông $K \times K$ .

Ban đầu, mỗi ô có giá trị đẹp bằng $0$ . Sau mỗi lần cập nhật giá trị đẹp của một con bò, hãy tìm độ hấp dẫn lớn nhất — tức là tổng giá trị đẹp lớn nhất trong tất cả các vùng $K \times K$ có thể.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $K$
Dòng 2: Số nguyên $Q$ — số lần cập nhật
$Q$ dòng tiếp theo, mỗi dòng gồm 3 số nguyên $r$ , $c$ , $v$ : đặt giá trị đẹp của ô $(r, c)$ thành $v$

Dữ liệu ra

$Q$ dòng, mỗi dòng là độ hấp dẫn lớn nhất sau lần cập nhật tương ứng.

Ràng buộc

$1 \leq N \leq 500$
$1 \leq K \leq min (N, 25)$
$1 \leq Q \leq 3 \times 10^{4}$
$1 \leq v \leq 10^{6}$
$1 \leq r, c \leq N$

Ví dụ

Input	Output	Giải thích
4 2 3 2 2 11 3 4 3 3 1 100	11 11 111	Vùng $2 \times 2$ tốt nhất ban đầu chứa ô (2,2)=11. Sau cập nhật cuối, vùng (2,1)-(3,2) có tổng 111.
3 1 3 2 2 3 2 2 5 2 2 7	3 5 7	$K = 1$ nên mỗi vùng chỉ 1 ô, đáp án là giá trị lớn nhất.

Bình luận

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