Submission #18138

#	Time	Username	Problem	Language	Result	Execution time	Memory
18138		tlwpdus	On grid (kriii2_O)	C++98	1 / 4	1000 ms	2208 KiB

O

#include<stdio.h>
#include<algorithm>

using namespace std;

int r, c;
int map[310][310];
int psum[310][310];
int dyn[310][310];

void process() {
	int i, j, k, l, maxi;
	for (i=0;i<r;i++) for (j=0;j<c;j++) {
		if (i==0&&j==0) psum[i][j] = map[i][j];
		else if (i==0) psum[i][j] = psum[i][j-1]+map[i][j];
		else if (j==0) psum[i][j] = psum[i-1][j]+map[i][j];
		else psum[i][j] = psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+map[i][j];
	}
	for (i=0;i<r;i++) for (j=0;j<c;j++) {
		if (i==0||j==0) dyn[i][j] = psum[i][j];
		else {
			maxi = psum[i][j];
			for (k=0;k<i;k++) for (l=0;l<j;l++) {
				maxi = max(maxi,dyn[k][l]+psum[i][j]-psum[k][j]-psum[i][l]+psum[k][l]);
			}
			dyn[i][j] = maxi;
		}
	}
	printf("%d\n",dyn[r-1][c-1]);
}

void input() {
	int i, j;
	scanf("%d %d",&r,&c);
	for (i=0;i<r;i++) {
		for (j=0;j<c;j++) {
			scanf("%d",&map[i][j]);
		}
	}
}

int main() {
	input();
	process();
	return 0;
}

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