[THHV 2017 - CHY - 10] Bài 3: Chọn ô
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho một bảng hình chữ nhật kích thước ~5 \times n~ ô vuông. Các dòng được đánh số từ 1 đến 5, từ trên xuống dưới, các cột được đánh số từ 1 đến ~n~ từ trái qua phải. Ô nằm trên giao của dòng ~i~ và cột ~j~ được gọi là ô ~(i,j)~. Trên mỗi ô ~(i,j)~ có ghi một số nguyên ~A_{ij}~, ~i = 1, 2, 3, 4, 5~; ~j = 1, 2, \dots, n~. Một cách chọn ô là việc xác định một tập con khác rỗng ~S~ của tập tất cả các ô của bảng sao cho không có hai ô nào trong ~S~ có chung cạnh. Các ô trong tập ~S~ được gọi là ô được chọn, tổng các số trong các ô được chọn được gọi là trọng lượng của cách chọn.
Yêu cầu: Tìm cách chọn sao cho trọng lượng là lớn nhất.
Input
- Dòng đầu tiên chứa số nguyên dương ~n~ là số cột của bảng.
- Cột thứ ~j~ trong số ~n~ cột tiếp theo chứa 5 số nguyên ~a_{1j}, a_{2j}, a_{3j}, a_{4j}, a_{5j}~ hai số liên tiếp cách nhau ít nhất một dấu cách, là 5 số trên cột ~j~ của bảng.
Output
- Gồm 1 dòng duy nhất là trọng lượng của cách chọn tìm được.
Sample Input 1
3
-1 9 3
-4 5 -6
7 8 9
9 7 2
9 4 9
Sample Output 1
50
Bình luận
Test ví dụ đúng nhưng giải thích của ví dụ bị sai.
Các ô cần chọn là (3, 1), (5, 1), (1, 2), (4, 2), (3, 3), (5, 3) tổng bằng 7 + 9 + 9 + 7 + 9 + 9 = 50.