Gửi bài giải
Điểm:
0,00 (OI)
Giới hạn thời gian:
4.0s
Giới hạn bộ nhớ:
512M
Input:
BOARD.INP
Output:
BOARD.OUT
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho một bảng kích thước ~n \times m~: có ~n~ hàng và ~m~ cột. Ta gọi giá trị của ô nằm trên hàng ~x~ ~(1 \leq x \leq n)~ và cột ~y~ ~(1 \leq y \leq m)~ là ~a_{x,\ y}~.
Bạn được phép chọn một số ô với quy tắc: Nếu ô ~(p,\ q)~ được chọn thì các ô ~(p - 1,\ q)~ và ~(p,\ q - 1)~ (nếu tồn tại trong bảng) sẽ không thể được chọn nữa. Hay nói cách khác: không được chọn hai ô mà có một ô nằm ngay bên trên hoặc bên trái ô còn lại.
Hãy tìm ra cách chọn sao cho tổng giá trị của các ô được chọn là lớn nhất có thể.
Dữ liệu - Nhập từ tệp văn bản BOARD.inp
:
- Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n \times m \leq 400)~.
- ~n~ dòng tiếp theo mỗi dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2},... , a_{i, m}~ ~(|a_{i, j}| \leq 10^9)~.
Kết quả - Ghi ra tệp văn bản BOARD.out
:
- Gồm một dòng duy nhất chứa kết quả bài toán.
Chấm điểm
Điểm | Ràng buộc bổ sung |
---|---|
~36~ | ~n = 1~ |
~26~ | ~n \times m \leq 20~ |
~22~ | ~n \le 10~ |
~16~ | Không có ràng buộc gì thêm |
Ví dụ
Dữ liệu (BOARD.inp
)
3 4
1 2 3 4
3 1 4 2
2 3 1 4
Kết quả (BOARD.out
)
20
Giải thích
- Ta chọn các ô ~(1, 2)~, ~(1, 4)~, ~(2, 1)~, ~(2, 3)~, ~(3, 2)~ và ~(3, 4)~, khi đó kết quả là ~2 + 4 + 3 + 4 + 3 + 4 = 20~.
Dữ liệu (BOARD.inp
)
4 5
-7 -6 10 -6 -2
9 -3 -7 8 9
-8 -5 -9 -2 -1
-3 4 -4 -2 -6
Kết quả (BOARD.out
)
32
Dữ liệu (BOARD.inp
)
1 7
7 7 1 1 8 15 3
Kết quả (BOARD.out
)
23
Bình luận