oj.uz

Submission #9711

# Submission time Handle Problem Language Result Execution time Memory
9711 2014-09-28T08:18:09 Z shashack On grid (kriii2_O) C++
1 / 4
 1000 ms 3340 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3340 KB Output is correct
2 Correct 0 ms 3340 KB Output is correct
3 Correct 0 ms 3340 KB Output is correct
4 Correct 0 ms 3340 KB Output is correct
5 Correct 0 ms 3340 KB Output is correct
6 Correct 0 ms 3340 KB Output is correct
7 Correct 0 ms 3340 KB Output is correct
8 Correct 0 ms 3340 KB Output is correct
9 Correct 0 ms 3340 KB Output is correct
10 Correct 0 ms 3340 KB Output is correct
11 Correct 0 ms 3340 KB Output is correct
12 Correct 0 ms 3340 KB Output is correct
13 Correct 0 ms 3340 KB Output is correct
14 Correct 0 ms 3340 KB Output is correct
15 Correct 0 ms 3340 KB Output is correct
16 Correct 0 ms 3340 KB Output is correct
17 Correct 0 ms 3340 KB Output is correct
18 Correct 0 ms 3340 KB Output is correct
19 Correct 0 ms 3340 KB Output is correct
20 Correct 0 ms 3340 KB Output is correct
21 Correct 0 ms 3340 KB Output is correct
22 Correct 0 ms 3340 KB Output is correct
23 Correct 0 ms 3340 KB Output is correct
24 Correct 0 ms 3340 KB Output is correct
25 Correct 0 ms 3340 KB Output is correct
26 Correct 0 ms 3340 KB Output is correct
27 Correct 0 ms 3340 KB Output is correct
28 Correct 0 ms 3340 KB Output is correct
29 Correct 0 ms 3340 KB Output is correct
30 Correct 0 ms 3340 KB Output is correct

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3340 KB Program timed out
2 Halted 0 ms 0 KB -