| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P154PROD - ROUND 4D - Di chuyển tăng |
Cooper đang chơi trận địa xe tăng với TARS, các anh chơi trên tấm bản đồ là ma trận a với n hàng và m cột, ô a[i][j] có một số điểm mà khi ai di chuyển xe tăng qua sẽ được cộng số điểm ấy vào số điểm của mình sau khi kết thúc trò chơi.
Ban đầu cả số điểm cả hai đều bằng 0, Cooper di chuyển từ ô a[1][1] đến ô a[n][m], sau khi ăn điểm ở ô a[i][j] thì anh sẽ di chuyển đến một trong hai ô a[i][j+1] hoặc a[i+1][j], TARS di chuyển từ ô a[n][1] xuống ô a[1][m], sau khi đến ô a[i][j] thì anh sẽ di chuyển đến một trong hai ô a[i][j+1] hoặc a[i-1][j], các xe tăng luôn di chuyển bên trong bản đồ. Có một quy tắc là hai xe tăng chỉ có thể cùng đi qua một ô duy nhất và ô đấy sẽ không tính điểm cho cả 2.
CASE đứng ngoài theo dõi và anh đang tự đặt ra một câu hỏi là tổng số điểm cao nhất của cả Cooper và TARS cộng lại là bao nhiêu.
Hãy giúp anh ấy.
Input
Dòng đầu tiên chứa hai số tự nhiên n và m (3 ≤ n, m ≤ 1000).
n dòng sau dòng thứ i chứa m số nguyên không âm, số thứ j là a[i][j] - số điểm ở ô (i, j)
(0 ≤ a[i][j]≤ 100 000).
Output
Một dòng duy nhất chứa kết quả của bài toán.
Example
Input:3 3
100 100 100
100 1 100
100 100 100 Output: 800
Cooper sẽ di chuyển từ a[1][1] → a[1][2] → a[2][2] → a[3][2] → a[3][3], TARS sẽ di chuyển từ a[3][1] → a[2][1] → a[2][2] → a[2][3] → a[1][3].
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-25 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
