F1 - Đua xe công thức 1
Giới hạn- Thời gian: 0.075s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Các bạn chắc đều biết đến môn thể thao đua xe công thức 1 - môn thể thao của tốc độ. Tuy nhiên, thời gian gần đây, để tăng tính hấp dẫn của môn thể thao này, BTC quyết định thay đổi luật lệ chơi. Các tay đua sẽ đua xe trong một khu vực hình chữ nhật chia làm M x N ô nhỏ. Ở mỗi ô có một điểm số nhất định ( tất nhiên có thể là số âm, đó là các chướng ngại vật nguy hiểm ). Các tay đua xuất phát ở vị trí ô trái trên của bản đồ, có thể đi từ ô này sang ô khác kề cạnh nhưng không được phép rẽ trái, cũng không được phép đi vào ô đã từng đi qua. Tay đua có quyền quyết định kết thúc chặng đua ở bất cứ đâu. Sau khi kết thúc cuộc đua, ai là người có vận tốc nhanh nhất sẽ chiến thắng. Tuy nhiên, trong trường hợp 2 người có cùng vận tốc ( điều này rất hay xảy ra do thiết bị đo cũ kỹ, chỉ đo được với độ chính xác 100Km/h :D ), người nào đạt được nhiều điểm hơn sẽ chiến thắng. Điểm của từng tay đua sẽ bằng tổng điểm các ô tay đua đó đã đi qua. Bạn là một trong các vận động viên tham gia cuộc đua này, hãy tính toán xem đường đua nào sẽ đem lại cho bạn nhiều điểm nhất.
Input
Dòng đầu ghi 2 số M, N lần lượt là 2 kích thước của bản đồ ( M, N <= 20 ). M dòng sau mỗi dòng ghi N số là điểm số của ô tương ứng. Điểm số nằm trong khoảng từ -100 đến 100.
Output
Một số duy nhất là điểm số lớn nhất có thể đạt được.
Example
Input: 2 2 -33 37 15 -5 Output: 14
- Người up: beo_map
- Nguồn bài: (none)