topToBottom Samsung

#include <iostream>
using namespace std;
#define n 1000

int maxSum(int a[][n], int r, int c){
    int dp[n][n];

    for(int i=0; i<r; i++)
        for(int j=0; j<c; j++)
            dp[i][j]=0;

    dp[0][0]=a[0][0];

    for(int i=1; i<c; i++) dp[0][i]= dp[0][i-1] + a[0][i];

    for(int i=1; i<r; i++) dp[i][0]= dp[i-1][0] + a[i][0];

    for(int i=1; i<r; i++){
        for(int j=1; j<c; j++){
            dp[i][j]=max(dp[i-1][j], dp[i][j-1])  + a[i][j];
        }
    }
    return dp[r-1][c-1];
}
int main() {
    int t;
    cin>>t;
    while(t--){
        int r,c;
        cin>>r>>c;
        int a[n][n];
        for(int i=0; i<r; i++)
            for(int j=0; j<c; j++)
                cin>>a[i][j];

        cout<<maxSum(a,r,c)<<endl;
    }
}