Submission #1792751

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
#define p pair<int,int>
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
using namespace std;
int POW(int x,int y){return int(pow(double(x),double(y)));}
int fun(int x,int y,vector<vector<int>> d,int n,vector<vector<int>> b){
	int ma=0;
	rep(i,n-x+1){
		rep(j,n-y+1){
			if(i==0 && j==0) ma=max(ma,b[x-1][y-1]);
			else if(i==0) ma=max(ma,b[i+x-1][j+y-1]-b[i+x-1][j-1]);
			else if(j==0) ma=max(ma,b[i+x-1][j+y-1]-b[i-1][j+y-1]);
			else ma=max(ma,b[i+x-1][j+y-1]-b[i+x-1][j-1]-b[i-1][j+y-1]+b[i-1][j-1]);
		}
	}
	return ma;
}



int main(){
	int n;
	cin>>n;
	vector<vector<int>> d(n),a(n+1),b(n);
	rep(i,n){
		d[i].resize(n);
		b[i].resize(n);
		rep(j,n){
			cin>>d[i][j];
		}
	}
	rep(i,n+1){
		a[i].resize(n+1);
		rep(j,n+1){
			a[i][j]=-1;
		}
	}

	rep(i,n){
		rep(j,n){
			if(i==0 && j==0) b[0][0]=d[0][0];
			else if(i==0) b[0][j]=b[0][j-1]+d[0][j];
			else if(j==0) b[i][0]=b[i-1][0]+d[i][0];
			else b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+d[i][j];
		}
	}
			


	int q;
	cin>>q;
	vector<int> ans(q);
	rep(i,q){
		int x;
		cin>>x;
		int ma=0;
		FOR(j,1,n+1){
			int y=min(x/j,n);
			if(y==0){
				break;
			}
			if(a[j][y]!=-1){
				ma=max(ma,a[j][y]);
			}else{
				//j * x/j の最大を見つけて保存,比較
				a[j][y]=fun(j,y,d,n,b);
				ma=max(ma,a[j][y]);
			}
		}
		ans[i]=ma;
	}
	rep(i,q){
		cout<<ans[i]<<endl;
	}
	
}

Submission Info

Judge Result