Submission #9711

#	Time	Username	Problem	Language	Result	Execution time	Memory
9711		shashack	On grid (kriii2_O)	C++98	1 / 4	1000 ms	3340 KiB

O

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

int row, col;
const ll INF=9876543210000;
ll data[310][310], psum[310][310], cache[310][310];

ll get_psum(int sx, int sy, int ex, int ey)
{
	ll ret = psum[ex][ey] - psum[sx-1][ey] - psum[ex][sy-1] + psum[sx-1][sy-1];
	return ret;
}

ll solution(int x, int y)
{
	if(x==row+1 && y==col+1) return 0;
	else if(x==row+1 || y==col+1) return -INF;

	ll& ret=cache[x][y];
	if(ret!=-INF) return ret;

	for(int i=x ; i<=row ; i++)
		for(int j=y ; j<=col ; j++)
			ret=max(ret, solution(i+1, j+1)+get_psum(x, y, i, j));

	return ret;
}

int main(void)
{
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d%d", &row, &col);
	for(int i=1 ; i<=row ; i++)
		for(int j=1 ; j<=col ; j++)
			scanf("%lld", &data[i][j]);

	for(int i=0 ; i<310 ; i++)
		for(int j=0 ; j<310 ; j++)
			cache[i][j]=-INF;

	for(int i=1 ; i<=row ; i++)
		for(int j=1 ; j<=col ; j++)
			psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + data[i][j];

	ll sol=solution(1, 1);
	printf("%lld\n", sol);
}

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