Submission #2203875

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <cmath>
#define rep(i, a, n) for(int i = a;i < n;i++)
#define repe(i, a, n) for(int i = a;i <= n;i++)
#define repr(i, a, n) for(int i = a;i > n;i--)
#define INF 999999999
using namespace std;


int n;
int d[60][60];
int q;
int p[2510];
int ans[2510];


void makeAcc(){
	rep(i, 0, n)
		rep(j, 1, n) d[i][j] += d[i][j-1];
	rep(i, 1, n)
		rep(j, 0, n) d[i][j] += d[i-1][j];
}


int acc(int i1, int j1, int i2, int j2){
	if(i1-1 < 0 && j1-1 < 0) return d[i2][j2];
	if(i1-1 < 0) return d[i2][j2] - d[i2][j1-1];
	if(j1-1 < 0) return d[i2][j2] - d[i1-1][j2];
	return d[i2][j2] - d[i2][j1-1] - d[i1-1][j2] + d[i1-1][j1-1];
}


void makeAns(){
	rep(i1, 0, n)
		rep(j1, 0, n)
			rep(i2, i1, n)
				rep(j2, j1, n)
					ans[(i2-i1+1)*(j2-j1+1)] = max(ans[(i2-i1+1)*(j2-j1+1)], acc(i1, j1, i2, j2));
	repe(i, 2, n*n){
		ans[i] = max(ans[i], ans[i-1]);
	}
}


void solve(){
	rep(i, 0, q)
		cout << ans[p[i]] << endl;
}


int main(){
	cin >> n;
	rep(i, 0, n)
		rep(j, 0, n) cin >> d[i][j];
	cin >> q;
	rep(i, 0, q) cin >> p[i];

	makeAcc();

	makeAns();

	solve();

	return 0;
}

Submission Info

Judge Result