Submission #340219

---

Source Code Expand

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
int N,Q,P,nn;
int rect[50][50][51][51];
int opt[2501];

int main(void){
	cin >> N;
	nn = N*N+1;
	rep(i, 0, N)rep(j, 0, N){
		cin >> rect[i][j][0][0];
		opt[1] = max(opt[1], rect[i][j][0][0]);
	}
	
	rep(h, 1, N){
		rep(i,0,N)
			rep(j, 0, N - h){
				rect[i][j][0][h] = rect[i][j][0][h - 1] + rect[i][j + h][0][0];
				opt[h+1] = max(opt[h+1], rect[i][j][0][h]);
			}
	}
	rep(h, 0, N){
		rep(w, 1, N){
			int area = (w + 1)*(h + 1);
			rep(i,0,N-w)
				rep(j, 0, N - h){
					rect[i][j][w][h] = rect[i][j][w - 1][h] + rect[i + w][j][0][h];
					opt[area] = max(opt[area], rect[i][j][w][h]);
				}
		}
	}
	rep(i, 1, nn)
		opt[i] = max(opt[i - 1], opt[i]);

	cin >> Q;
	rep(i, 0, Q){
		cin >> P;
		cout << opt[P] << endl;
	}

}

Submission Info

Judge Result