Submission #1591005

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int n, q, d[55][55], s[55][55], dp[2505];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) cin >> d[i][j];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + d[i][j];
		}
	}
	for (int i = 1; i <= n*n; i++) {
		int ma = 0;
		for (int j = 1; j*j <= i; j++) {
			if (i%j == 0 && i/j <= n) {
				for (int x = 1; x+j-1 <= n; x++) {
					for (int y = 1; y+i/j-1 <= n; y++) {
						ma = max(ma, s[x+j-1][y+i/j-1]-s[x-1][y+i/j-1]-s[x+j-1][y-1]+s[x-1][y-1]);
					}
				}
				for (int x = 1; x+i/j-1 <= n; x++) {
					for (int y = 1; y+j-1 <= n; y++) {
						ma = max(ma, s[x+i/j-1][y+j-1]-s[x-1][y+j-1]-s[x+i/j-1][y-1]+s[x-1][y-1]);
					}
				}
			}
		}
		dp[i] = max(ma, dp[i-1]);
	}
	cin >> q;
	vector<int> ans(q);
	FOR(i, q) {
		int p;
		cin >> p;
		ans[i] = dp[p];
	}
	FOR(i, q) cout << ans[i] << endl;
	return 0;
}

Submission Info

Judge Result