Submission #617700

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int h, w;
long long x[55][55];
long long y[55][55];

long long dp[55][55][55][55], maxn = -1000000000000000LL;

int main() {
	memset(dp, 0, sizeof(dp));
	cin >> h >> w;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> x[i][j];
			y[i][j] = y[i][j - 1] + x[i][j];
		}
	}
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			dp[i][j][i][j] = x[i][j];
			for (int k = i; k <= h; k++) {
				for (int l = j; l <= w; l++) {
					dp[i][j][k][l] = max(dp[i][j][k - 1][l] + (y[k][l] - y[k][j - 1]), x[k][l]);
				}
			}
		}
	}
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			for (int k = i; k <= w; k++){
				for (int l = j; l <= w; l++) {
					if (k != i && l != j) {
						dp[i][j][k][l] = max(dp[i][j][k][l], max(dp[i][j][k - 1][l], dp[i][j][k][l - 1]));
					}
					else if (k == i) {
						dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1]);
					}
					else if (l == j) {
						dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l]);
					}
				}
			}
		}
	}
	for (int i = 1; i <= h; i++){
		for (int j = 1; j <= w; j++) {
			for (int k = 1; k <= h; k++) {
				for (int l = 1; l <= w; l++) {
					if (i < k || j < l) {
						maxn = max(maxn, dp[1][1][i][j] + dp[k][l][h][w]);
					}
				}
			}
		}
	}
	cout << maxn << endl;
	return 0;
}

Submission Info

Judge Result