21802022-12-29 10:38:17lacitoTáblatöréscpp11Accepted 50/5028ms15628 KiB
#include <bits/stdc++.h>
using namespace std;

int tabla[30][30];
pair<int, int> dp[30][30][30][30];

pair<int, int> szamol(int bfi, int bfj, int jai, int jaj) {
	if (bfi > jai) return make_pair(0, 0);
	if (bfj > jaj) return make_pair(0, 0);
	if (dp[bfi][bfj][jai][jaj] != make_pair(0, 0)) return dp[bfi][bfj][jai][jaj];
	int osszf = 0;
	for (int j = bfj; j <= jaj; j++) osszf += tabla[bfi][j]; 
	pair<int, int> felso_nelkul = szamol(bfi + 1, bfj, jai, jaj);
	pair<int, int> felso = {osszf + felso_nelkul.second, felso_nelkul.first};
	int ossza = 0;
	for (int j = bfj; j <= jaj; j++) ossza += tabla[jai][j]; 
	pair<int, int> also_nelkul = szamol(bfi, bfj, jai - 1, jaj);
	pair<int, int> also = {ossza + also_nelkul.second, also_nelkul.first};
	int osszb = 0;
	for (int i = bfi; i <= jai; i++) osszb += tabla[i][bfj]; 
	pair<int, int> bal_nelkul = szamol(bfi, bfj + 1, jai, jaj);
	pair<int, int> bal = {osszb + bal_nelkul.second, bal_nelkul.first};
	int osszj = 0;
	for (int i = bfi; i <= jai; i++) osszj += tabla[i][jaj]; 
	pair<int, int> jobb_nelkul = szamol(bfi, bfj, jai, jaj - 1);
	pair<int, int> jobb = {osszj + jobb_nelkul.second, jobb_nelkul.first};
	dp[bfi][bfj][jai][jaj] = max({felso, also, bal, jobb});
	return max({felso, also, bal, jobb});
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tabla[i][j];
		}
	}
	pair<int, int> mo = szamol(0, 0, n - 1, m - 1);
	cout << mo.first;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms2068 KiB
2Accepted0/021ms12208 KiB
3Accepted2/22ms2464 KiB
4Accepted2/22ms2840 KiB
5Accepted1/12ms2600 KiB
6Accepted1/13ms3784 KiB
7Accepted1/12ms3176 KiB
8Accepted2/23ms3824 KiB
9Accepted3/33ms4308 KiB
10Accepted3/37ms7156 KiB
11Accepted3/313ms10108 KiB
12Accepted3/313ms10312 KiB
13Accepted4/423ms13516 KiB
14Accepted4/421ms13580 KiB
15Accepted4/428ms15052 KiB
16Accepted5/528ms15000 KiB
17Accepted5/528ms15112 KiB
18Accepted5/528ms15340 KiB
19Accepted1/128ms15376 KiB
20Accepted1/128ms15628 KiB