Submission #3979398

---

Source Code Expand

#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)
#define rep_r(i,s,n)for(ll i=n-1;i>=s;i--)
#define repe_r(i,s,n)for(ll i=s;i<=n;i++)
static const ll MOD = 1e9 + 7;
static const double PI = 3.141592653589793;
static const ll MAX_L = (ll)1 << 62;

ll d[51][51] = {};
ll s[51][51] = {};

int main() {
	ll n; cin >> n;
	repe(i, 1, n)repe(j, 1, n)cin >> d[i][j];
	repe(i, 1, n)repe(j, 1, n) {
		s[i][j] += d[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
	}

	ll q; cin >> q;

	ll ans[2501] = {};
	repe(i, 1, n)repe(j, 1, n)repe(k, i, n)repe(l, j, n) {
		ll square = (k - i + 1)*(l - j + 1);
		ans[square] = max(ans[square], s[k][l] + s[i - 1][j - 1] - s[k][j - 1] - s[i - 1][l]);
	}

	rep(i, 1, 2501) {
		ans[i] = max(ans[i - 1], ans[i]);
	}
	rep(i, 0, q) {
		ll p; cin >> p;
		cout << ans[p] << endl;
	}

	return 0;
}

Submission Info

Judge Result