Submission #6907260

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int n, d[55][55], cum[55][55], ma[2505];

int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> d[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cum[i+1][j+1] = cum[i][j+1] + cum[i+1][j] - cum[i][j] + d[i][j];
        }
    }
    for(int i1=0;i1<n;i1++){
        for(int j1=0;j1<n;j1++){
            for(int i2=i1+1;i2<=n;i2++){
                for(int j2=j1+1;j2<=n;j2++){
                    int s = (i2-i1)*(j2-j1);
                    ma[s] = max(ma[s], cum[i2][j2]-cum[i1][j2]-cum[i2][j1]+cum[i1][j1]);
                }
            }
        }
    }
    for(int i=0;i<n*n;i++){
        ma[i+1] = max(ma[i+1],ma[i]);
    }
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        int p;
        cin >> p;
        cout << ma[p] << endl;
    }
    return 0;
}

Submission Info

Judge Result