Submission #616771

---

Source Code Expand

#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;

const int My_Inf=2147483647;
const long long int My_LInf=9223372036854775807;
vector<long long int> divisor(long long int n) {
	vector<long long int> res;
	for (long long int i = 1; i * i <= n; ++i) {
		if (n % i == 0) {
			res.push_back(i);
			if (i * i != n) res.push_back(n / i);
		}
	}
	sort(begin(res), end(res));
	return res;
}
struct edge {
	int from;
	int to;
	int cost;
};
long long  int dp[51][51][51][51];
vector<vector<long long int>> widthmax(51, vector<long long int>(51,-9999999999999999));
vector<vector<long long int >> heightmax(51,vector<long long int>(51, - 9999999999999999));
int main() {
	memset(dp, 0, sizeof(dp));
	/*
	int N; cin >> N;
	vector<int>nums;
	nums.push_back(My_Inf);
	for (int i = 0; i < N - 1; ++i) {
		int a; cin >> a;
		nums.push_back(a);
	}
	nums.push_back(My_Inf);
	for (int i = 0; i < N; ++i) {
		cout << min(nums[i], nums[i + 1]);
		if (i != N - 1)cout << " ";
	}
	cout << endl;
	return 0;
	int N, M, S, D; cin >> N >> M >> S >> D;
	for (int i = 0; i < M; ++i) {
		int L; cin >> L;
		vector<int>ss;
		for (int i = 0; i < L; ++i) {
			int s; cin >> s;
			ss.push_back(s);
		}
		vector<int>ws;
		vector<edge>edges;
		for (int i = 0; i < L - 1; ++i) {
			int w; cin >> w;
			ws.push_back(w);
		}
		for (int i = 0; i < L - 1; ++i) {
			edges.push_back(edge{ss[i],ss[i+1]})
		}
	}*/
	int H, W; cin >> H >> W;
	vector<vector<long long int>>field(H,vector<long long int>(W));
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			int a; cin >> a;
			field[i][j] = a;
		}
	}
	vector<vector<long long int>>sums(H+1, vector<long long int>(W+1));
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + field[i][j];
		}
	}
	for (int l = 0; l <= W; ++l) {
		for (int r = l+1; r <= W; ++r) {
			for (int u = 0; u <= H; ++u) {
				for (int d = u+1; d <= H; ++d) {
					dp[l][r][u][d] = sums[d][r] - sums[u][r] - sums[d][l] + sums[u][l];
				}
			}
		}
	}
	for (int a = 1; a <= W; ++a) {
		for (int w = 0; w <= W-a; ++w) {
			if (a != 1) {
				widthmax[w][w + a] = max(widthmax[w][w + a - 1], widthmax[w + 1][w + a]);
			}
			for (int u = 0; u <= H; ++u) {
				for (int d = u+1; d <= H; ++d) {
					widthmax[w][w + a] = max(widthmax[w][w + a], dp[w][w + a][u][d]);
				}
			}
		}
	}
	
	for (int a = 1; a <= H; ++a) {
		for (int w = 0; w <= H - a; ++w) {
			if (a != 1) {
				heightmax[w][w + a] = max(heightmax[w][w + a - 1], heightmax[w + 1][w + a]);
			}
			for (int u = 0; u <= W; ++u) {
				for (int d = u+1; d <= W; ++d) {
					heightmax[w][w + a] = max(heightmax[w][w + a], dp[u][d][w][w + a]);
				}
			}
		}
	}
	long long int ans = -9999999999999999;
	for (int L = 1; L < W; ++L) {
		long long int nans = 0;
		nans += widthmax[0][L]+widthmax[L][W];
		ans = max(ans, nans);
	}
	for (int L = 1; L < H; ++L) {
		long long int nans = 0;
		nans += heightmax[0][L] + heightmax[L][H];
		ans = max(ans, nans);
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result