Submission #149038

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

void solve()
{
	int N;
	cin >> N;
	vector< vector<int> > D(N + 1, vector<int>(N + 1));
	for(int i = 1; i <= N; ++i)
	{
		for(int j = 1; j <= N; ++j)
		{
			cin >> D[i][j];
		}
	}
	
	for(int i = 0; i <= N; ++i)
	{
		for(int j = 1; j <= N; ++j)
		{
			D[i][j] += D[i][j - 1];
		}
	}
	for(int j = 0; j <= N; ++j)
	{
		for(int i = 1; i <= N; ++i)
		{
			D[i][j] += D[i - 1][j];
		}
	}

	vector<int> res(N * N + 1);
	for(int u = 1; u <= N; ++u)
	{
		for(int b = 0; b < u; ++b)
		{
			for(int r = 1; r <= N; ++r)
			{
				for(int l = 0; l < r; ++l)
				{
					res[(r - l) * (u - b)] = max(res[(r - l) * (u - b)], D[u][r] - D[b][r] - D[u][l] + D[b][l]);
				}
			}
		}
	}
	
	int size = N * N;
	for(int i = 1; i <= size; ++i)
	{
		res[i] = max(res[i], res[i - 1]);
	}
	int Q;
	cin >> Q;
	for(int i = 0; i < Q; ++i)
	{
		int p;
		cin >> p;
		cout << res[p] << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Submission Info

Judge Result