Tổng lớn nhất chia hết
Đề bài
Mô tả
Cho ma trận kích thước gồm các số nguyên được sinh ngẫu nhiên đều trong đoạn . Các hàng được đánh số từ đến , các cột được đánh số từ đến .
Gọi là tổng các phần tử của hình chữ nhật con từ hàng đến hàng và từ cột đến cột :
Hãy tìm giá trị lớn nhất của chia hết cho .
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , và (, ).
- dòng tiếp theo, mỗi dòng chứa số nguyên trong đoạn .
Dữ liệu ra
In ra một số nguyên là tổng lớn nhất tìm được mà chia hết cho . Nếu không có hình chữ nhật nào thỏa mãn, in ra .
Ràng buộc
- Các phần tử của ma trận được sinh ngẫu nhiên đều, độc lập trong (trừ các ví dụ).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 7 5 1 2 0 0 3 3 1 3 0 3 1 0 1 2 1 1 0 2 0 3 2 2 4 1 4 4 0 3 0 2 3 0 2 2 1 0 0 3 0 1 0 4 |
65 | Ví dụ của đề gốc. |
| 3 3 10 3 9 4 8 1 6 7 5 2 |
20 | Ví dụ bổ sung, tính bằng lời giải mẫu. Hình chữ nhật hàng đến , cột đến có tổng . Tổng cả ma trận là , không có hình nào có tổng hoặc . |
Bình luận