Submission #9671

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9671	2014-09-28T08:00:25 Z	corea	On grid (kriii2_O)	C++14	1 / 4	1000 ms	225880 KB

O

#include <cstdio>
#include <iostream>
#include <cstring>
#include <tuple>
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;
 
#define REP(i, n) for(int i=0; i < n; ++i)

int n, m;
int a[305][305];

long long S[305][305];
long long V[305][305];
long long C[305][305];
long long M[305][305][305];

long long go() {

	memset(C, 0, sizeof(C));
	memset(M, 0, sizeof(M));
	memset(V, 0, sizeof(V));

	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= m; ++ j) {
			S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
		}
	}

	const long long INF = 1LL << 50;
	for(int i = 1; i <= n; ++ i) {
		V[i][0] = -INF;
		C[i][0] = -INF;
	}
	for(int j = 1; j <= m; ++ j) {
		V[0][j] = -INF;
		C[0][j] = -INF;
	}
	
	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= m; ++ j) {

			V[i][j] = -987987;
			for(int k = 0; k < i; ++ k) {
				for(int l = 0; l < j; ++ l) {
					V[i][j] = max(V[i][j], V[k][l] - S[i][l] - S[k][j] + S[k][l] + S[i][j]);
				}
			}

		}
	}
	return V[n][m];
}

int main() {
	while(cin >> n >> m && n && m ) {
		for(int i = 1; i <= n; ++ i) {
			for(int j=1; j<=m; ++j) {
				cin >> a[i][j];
			}
		}
		cout << go() << endl;
	}

	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	225880 KB	Output is correct
2	Correct	36 ms	225880 KB	Output is correct
3	Correct	60 ms	225880 KB	Output is correct
4	Correct	44 ms	225880 KB	Output is correct
5	Correct	80 ms	225880 KB	Output is correct
6	Correct	36 ms	225880 KB	Output is correct
7	Correct	76 ms	225880 KB	Output is correct
8	Correct	56 ms	225880 KB	Output is correct
9	Correct	72 ms	225880 KB	Output is correct
10	Correct	24 ms	225880 KB	Output is correct
11	Correct	40 ms	225880 KB	Output is correct
12	Correct	48 ms	225880 KB	Output is correct
13	Correct	68 ms	225880 KB	Output is correct
14	Correct	44 ms	225880 KB	Output is correct
15	Correct	52 ms	225880 KB	Output is correct
16	Correct	36 ms	225880 KB	Output is correct
17	Correct	52 ms	225880 KB	Output is correct
18	Correct	40 ms	225880 KB	Output is correct
19	Correct	44 ms	225880 KB	Output is correct
20	Correct	32 ms	225880 KB	Output is correct
21	Correct	60 ms	225880 KB	Output is correct
22	Correct	52 ms	225880 KB	Output is correct
23	Correct	48 ms	225880 KB	Output is correct
24	Correct	48 ms	225880 KB	Output is correct
25	Correct	44 ms	225880 KB	Output is correct
26	Correct	56 ms	225880 KB	Output is correct
27	Correct	48 ms	225880 KB	Output is correct
28	Correct	60 ms	225880 KB	Output is correct
29	Correct	56 ms	225880 KB	Output is correct
30	Correct	68 ms	225880 KB	Output is correct

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	460 ms	225880 KB	Output is correct
2	Correct	208 ms	225880 KB	Output is correct
3	Correct	728 ms	225880 KB	Output is correct
4	Correct	452 ms	225880 KB	Output is correct
5	Correct	232 ms	225880 KB	Output is correct
6	Execution timed out	1000 ms	225880 KB	Program timed out
7	Halted	0 ms	0 KB	-