Submission #13555

#TimeUsernameProblemLanguageResultExecution timeMemory
13555baneling100On grid (kriii2_O)C++98
4 / 4
64 ms1792 KiB
#include <stdio.h>
#include <algorithm>
#define R_MAX 300
#define C_MAX 300
#define INF 1000000000

using namespace std;

int R, C, G[R_MAX+1][C_MAX+1], D[R_MAX+1][C_MAX+1], K[R_MAX+1];

int main(void) {

    int i, j, k, sum;

    scanf("%d %d",&R,&C);
    for(i=1 ; i<=R ; i++) for(j=1 ; j<=C ; j++) {
        scanf("%d",&G[i][j]);
        D[i][j]=-INF;
    }
    for(i=1 ; i<=R ; i++) D[i][0]=-INF;
    for(i=1 ; i<=C ; i++) D[0][i]=-INF;
    for(i=1 ; i<=R ; i++) {
        for(j=1 ; j<=i ; j++) K[j]=-INF;
        for(j=1 ; j<=C ; j++) {
            sum=0;
            for(k=i ; k>=1 ; k--) {
                sum+=G[k][j];
                K[k]=max(K[k],D[k-1][j-1])+sum;
                D[i][j]=max(D[i][j],K[k]);
            }
        }
    }
    printf("%d",D[R][C]);

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...