1 solutions

  • 0
    @ 2024-12-5 18:12:20

    C++ :

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn=1005;
    int n,m,a[maxn][maxn];
    long long dp[maxn][maxn][3];
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            dp[i][1][2]=dp[i-1][1][2]+a[i][1];
        }
        for(int j=2;j<=m;j++){
            dp[1][j][0]=dp[1][j-1][2]+a[1][j];
            for(int i=2;i<=n;i++){
                dp[i][j][0]=max(dp[i][j-1][2],dp[i-1][j][0])+a[i][j];
            }
            dp[n][j][1]=dp[n][j-1][2]+a[n][j];
            for(int i=n-1;i>=1;i--){
                dp[i][j][1]=max(dp[i][j-1][2],dp[i+1][j][1])+a[i][j];
            }
            for(int i=1;i<=n;i++){
                dp[i][j][2]=max(dp[i][j][0],dp[i][j][1]);
            }
        }
        cout<<dp[n][m][2];
        return 0;
    } 
    
    • 1

    Information

    ID
    9125
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By