CHOOSE - Chọn phần tử
View as PDF
Submit solution
Points:
400.00
Time limit:
1.0s
Memory limit:
1000M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Cho ma trận ~A~ có ~N × M~ phần tử. Phần tử ở hàng ~i~ cột ~j~ có giá trị là ~A_{i,j}~.
Bạn được chọn không quá ~\lfloor\frac{M}{2}\rfloor~ phần tử trên mỗi hàng. Bạn hãy chọn sao cho tổng các phần tử chia hết cho ~K~ và có tổng là lớn nhất.
Dữ liệu
- Dòng đầu tiên gồm số nguyên ~N,M,K (1≤ N,M,K ≤70)~.
- ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên biểu diễn cho ma trận ~A~. Dòng thứ ~i~ cột ~j~ có giá trị là ~A_{i,j}\ (1≤ A_{i,j} ≤70)~.
Kết quả
- Một số nguyên duy nhất thể hiện tổng các phần tử đã chọn.
Ví dụ
Sample Input 1
3 4 7
51 2 6 7
52 62 65 5
6 6 62 62
Sample Output 1
308
Giải thích
- Hàng 1 chọn 51 và 6
- Hàng 2 chọn 62 và 65
- Hàng 3 chọn 62 và 62
- Tổng các phần tử chọn là: ~51+6+62+65+62+62=308~ chia hết cho ~7~
Chấm điểm
- Subtask 1 (50% số test): ~1≤ N × M ≤20~
- Subtask 2 (50% số test): Không có ràng buộc gì thêm
Nguồn: Free Contest
Comments
FINALLY !!!!
Yeah awesome