Submission #7590751

---

Source Code Expand

#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;

int main()
{
	int N, Q;
	cin >> N;
	vector<vector<int>> D(N + 1, vector<int>(N + 1));
	rep(i, N)rep(j, N)cin >> D[i + 1][j + 1];
	cin >> Q;
	vector<int> P(Q);
	rep(i, Q)cin >> P[i];

	// imos
	rep(h, N + 1)rep(w, N)D[h][w + 1] += D[h][w];
	rep(w, N + 1)rep(h, N)D[h + 1][w] += D[h][w];

	// imos2
	vector<int> imos(N*N + 1, 0);
	rep(l, N)REP(r, l + 1, N + 1)rep(u, N)REP(d, u + 1, N + 1) {
		int score = D[d][r] - D[d][l] - D[u][r] + D[u][l];
		int area = (d - u)*(r - l);
		imos[area] = max(imos[area], score);
	}
	rep(i, N*N)imos[i + 1] = max(imos[i + 1], imos[i]);

	// query
	for (auto q : P) {
		cout << imos[q] << endl;
	}
	return 0;
}

Submission Info

Judge Result