Problem ID:
sumsquare
Points:
2 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Author:
Problem types
Máy tính của tập đoàn ~ABC~ vừa được phát hành ra thị trường bị dính mã độc. Điều này sẽ làm ảnh hưởng rất lớn đến danh tiếng của công ty nên ban quản trị quyết định mời những chuyên gia bảo mật giúp đỡ.
Bạn được cung cấp một bảng ~a~ có kích thước ~n \times m~ chứa các số không âm. Vùng chứa mã độc là một hình vuông nằm trong bảng sao cho tổng giá trị các ô thuộc hình vuông bằng ~x~.
Là một lập trình viên thiên tài, nhiệm vụ của bạn là tìm vùng chứa mã độc lớn nhất.
Dữ liệu vào
- Dòng đầu tiên chứa ~2~ số nguyên dương ~n, m~ ~(1 \le m, n \le 1500)~.
- Dòng thứ hai chứa một số nguyên dương ~x~ ~(1 \le x \le 10^{9})~.
- ~n~ dòng tiếp theo mỗi dòng chứa ~m~ số nguyên không âm có giá trị không vượt quá ~10^6~.
Dữ liệu ra
- Một dòng duy nhất chứa điện tích của vùng chứa mã độc lớn nhất tìm được (dữ liệu đảm bảo luôn tìm được một vùng chứa mã độc hợp lệ).
Ràng buộc
- Có ~20 \%~ số test ứng với ~n, m~ ~(1 \le m, n \le 10)~.
- Có ~40 \%~ số test ứng với ~n, m~ ~(10 \le m, n \le 500)~.
- Có ~40 \%~ số test không có rangd buộc gì thêm.
Ví dụ
Dữ liệu vào
4 5
9
8 2 8 0 2
3 0 8 5 3
1 4 3 0 7
7 2 1 5 8
Dữ liệu ra
4
Giải thích
Ở ví dụ, ta chọn được một hình vuông có cạnh bằng ~2~ bao gồm các ô ~(3, 3), (3, 4), (4, 3), (4, 4)~.
Comments