Submission #1800619

---

Source Code Expand

#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
//#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
#define mp make_pair
signed main(){
    int n; cin>>n;
    vector<vector<int>>graph(n,vector<int>(n,0));
    vector<vector<int>>sum(n,vector<int>(n,0));
    rep(i,n)rep(j,n)cin>>graph[i][j];
    sum=graph;
    rep(i,n)rep(j,n-1)sum[i][j+1]+=sum[i][j];
    int dp[2501]={0};
    for(int x=0;x<n;x++){
        for(int y=0;y<n;y++){
            for(int xl=1;xl<=n;xl++){
                for(int yl=1;yl<=n;yl++){
                    if(x+xl>n||y+yl>n)continue;
                    int temp=0;
                    rep(k,yl)temp+=sum[y+k][x+xl-1]-(x?sum[y+k][x-1]:0);
                    cmax(dp[(xl)*(yl)],temp);
                }
            }
        }
    }
    rep(i,2501)if(i)cmax(dp[i], dp[i-1]);
    int m; cin>>m;
    rep(i,m){
        int index; cin>>index;
        cout<<dp[index]<<endl;
    }
}

Submission Info

Judge Result