Submission #13555

#	Time	Username	Problem	Language	Result	Execution time	Memory
13555		baneling100	On grid (kriii2_O)	C++98	4 / 4	64 ms	1792 KiB

O

#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;
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3