Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Hai anh em An và Bình tham gia trò chơi thám hiểm trên bảng số XtremeMaze. Bảng có kích thước ~N \times M~ (~N~ dòng và ~M~ cột), các ô trong bảng được đánh số từ trái sang phải và từ trên xuống dưới.

Tại mỗi ô của bảng có ghi một số nguyên là số điểm kinh nghiệm mà người chơi sẽ nhận được khi đi vào ô này. Cần lưu ý là số điểm tại một số ô có thể là số âm; khi đó, điểm kinh nghiệm của người chơi sẽ bị giảm nếu đi vào ô này.

An và Bình bắt đầu tại ô trái trên, đánh số là ~(1, 1)~. Mỗi lượt, một người chỉ có thể di chuyển tới ô kề cạnh ngay phía dưới hoặc ô kề cạnh ngay bên phải và không được phép đi ra khỏi bảng. Khi đi qua mỗi ô, người chơi nhận được số điểm kinh nghiệm bằng số nguyên ghi ở ô đó. Hành trình kết thúc tại ô ~(N, M)~.

Mục tiêu của trò chơi này là hai anh em đạt được tổng số điểm cao nhất có thể. Theo quy định, các ô mà An và Bình đi qua không được phép trùng nhau, ngoại trừ ô bắt đầu tại vị trí ~(1, 1)~ và ô kết thúc tại vị trí ~(N, M)~. Quy ước: giá trị điểm kinh nghiệm tại ô ~(1, 1)~ và ô ~(N, M)~ đều bằng 0.

Yêu cầu: Hãy viết chương trình tính tổng số điểm kinh nghiệm lớn nhất mà An cùng với Bình đạt được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~N~ và ~M~ ~(2 \le N, M \le 200)~, số dòng và số cột của bảng.
• ~N~ dòng tiếp theo, mỗi dòng ghi ~M~ số nguyên là số điểm kinh nghiệm tại mỗi ô trên bảng. Điểm kinh nghiệm tại mỗi ô có giá trị tuyệt đối không vượt quá 100.

Kết quả

• Ghi ra duy nhất một số nguyên là tổng điểm lớn nhất mà An cùng với Bình đạt được.

Subtask

• ~30\%~ số điểm của bài tương ứng với các test có ~N \le 3~ và ~M \le 200~.
• ~40\%~ số điểm khác của bài tương ứng với các test có ~N \le 50~ và ~M \le 50~.
• ~30\%~ số điểm còn lại: ~N, M \le 200~.

Sample Input 1

3 3
0 2 3
4 5 6
7 8 0

Sample Output 1

32

Nguồn: Olympic 30/4 năm 2019 – Tin học khối 11 – Bài 2.