记录编号	606135	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3501.[CSP 2020J]方格取数	最终得分	100
用户昵称	金牌教师王艳芳	是否通过	通过
代码语言	C++	运行时间	1.952 s
提交时间	2025-09-16 22:45:16	内存使用	5.21 MiB

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1005;
const long long INF = -1e18;

int a[MAX][MAX];
long long dp0[MAX], dp1[MAX];
long long nd0[MAX], nd1[MAX];

int main() {
    freopen("csp2020pj_number.in", "r", stdin);
    freopen("csp2020pj_number.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    dp0[0] = a[0][0];
    for (int i = 1; i < n; ++i) {
        dp0[i] = dp0[i-1] + a[i][0];
    }
    for (int i = 0; i < n; ++i) {
        dp1[i] = INF;
    }
    dp1[0] = a[0][0];
    for (int j = 1; j < m; ++j) {
        for (int i = 0; i < n; ++i) {
            long long l = max(dp0[i], dp1[i]);
            long long u = (i > 0) ? nd0[i-1] : INF;
            nd0[i] = max(l, u) + a[i][j];
        }
        for (int i = n-1; i >= 0; --i) {
            long long l = max(dp0[i], dp1[i]);
            long long d = (i < n-1) ? nd1[i+1] : INF;
            nd1[i] = max(l, d) + a[i][j];
        }
        for (int i = 0; i < n; ++i) {
            dp0[i] = nd0[i];
            dp1[i] = nd1[i];
        }
    }
    cout << max(dp0[n-1], dp1[n-1]) << endl;
    return 0;
}