#1333. CHANGE2D - Biến đổi 2D

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Nguồn: Bài tập thầy Nguyễn Thanh Bình Ôn ĐT Hải Phòng T10/2020

Cho mảng hai chiều m hàng, n cột với các phần tử là các số nguyên. Thực hiện Q phép biến đổi trên mảng này, mỗi phép biến đổi mô tả bằng bộ 5 số nguyên (i_1,j_1,i_2,j_2,d) thể hiện việc tăng tất cả các phần tử trong hình chữ nhật con của mảng có ô góc trên-trái là (i_1,j_1) và ô góc dưới-phải là (i_2,j_2) lên d đơn vị.

Sau khi thực hiện các phép biến đổi, hãy tìm hình vuông kích thước k×k trên mảng có tổng lớn nhất.

Dữ liệu vào:

  • Dòng đầu chứa ba số nguyên dương m,n≤1000,1≤k≤min⁡(m,n) ;
  • m dòng tiếp theo, dòng thứ i chứa n số nguyên, số thứ j là giá trị ở ô (i,j) . Giá trị này có trị tuyệt đối không vượt quá 10^3 ;
  • Dòng tiếp theo chứa số nguyên dương Q≤10^5 ;
  • Q dòng cuối cùng, mỗi dòng chứa 5 số nguyên i_1,j_1,i_2,j_2,d mô tả một phép biến đổi

Dữ liệu ra:

  • Một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

Dữ liệu vào:
3 3 2
1 1 1
1 1 1
1 1 1
1
2 2 3 3 -1
Dữ liệu ra:
3

Giới hạn:

  • 50\% số test trong đó tất cả các số nguyên có giá trị tuyệt đối không vượt 100 .