67062023-12-17 17:31:19111Táblatöréscpp17Accepted 50/5014ms15724 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

#define pii pair<int, int>

int N, M;
int a[31][31];
int s[31][31];
int d[31][31][31][31];

int sum(int r1, int c1, int r2, int c2) {
	return s[r2][c2] - s[r2][c1] - s[r1][c2] + s[r1][c1];
}

int solve(int r1, int c1, int r2, int c2) {
	if (r1 == r2 || c1 == c2) {
		return 0;
	}
	if (d[r1][c1][r2][c2]) {
		return d[r1][c1][r2][c2];
	}
	int ans = 0;
	ans = max(ans, sum(r1, c2 - 1, r2, c2) + sum(r1, c1, r2, c2 - 1) - solve(r1, c1, r2, c2 - 1));
	ans = max(ans, sum(r1, c1, r2, c1 + 1) + sum(r1, c1 + 1, r2, c2) - solve(r1, c1 + 1, r2, c2));
	ans = max(ans, sum(r2 - 1, c1, r2, c2) + sum(r1, c1, r2 - 1, c2) - solve(r1, c1, r2 - 1, c2));
	ans = max(ans, sum(r1, c1, r1 + 1, c2) + sum(r1 + 1, c1, r2, c2) - solve(r1 + 1, c1, r2, c2));
	d[r1][c1][r2][c2] = ans;
	return ans;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifdef CB
	freopen("be2.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= M; j++) {
			for (int k = 0; k < i; k++) {
				for (int l = 0; l < j; l++) {
					s[i][j] += a[k][l];
				}
			}
		}
	}
	cout << solve(0, 0, N, M) << endl;
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms2100 KiB
2Accepted0/012ms12628 KiB
3Accepted2/23ms2600 KiB
4Accepted2/23ms2624 KiB
5Accepted1/13ms2556 KiB
6Accepted1/13ms3464 KiB
7Accepted1/13ms3068 KiB
8Accepted2/23ms3740 KiB
9Accepted3/33ms4488 KiB
10Accepted3/34ms7400 KiB
11Accepted3/38ms10312 KiB
12Accepted3/38ms10332 KiB
13Accepted4/412ms13640 KiB
14Accepted4/412ms13916 KiB
15Accepted4/414ms15536 KiB
16Accepted5/514ms15576 KiB
17Accepted5/514ms15596 KiB
18Accepted5/514ms15724 KiB
19Accepted1/114ms15668 KiB
20Accepted1/114ms15668 KiB