Submission #1443481

---

Source Code Expand

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

using namespace std;
using llng = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
template<class T> using hset = unordered_set<T>;
template<class Key, class T> using hmap = unordered_map<Key, T>;

int main() {
    int N; cin >> N;
    vvi B(N+1, vi(N+1,0));
    vi R(N*N+1, 0);
    int D;
    for (int i=1; i<=N; i++) for (int j=1; j<=N; j++) {
        cin >> D;
        B[i][j] = D + B[i-1][j] + B[i][j-1] - B[i-1][j-1];
    }
    for (int i=0; i<=N; i++) {
        for (int j=0; j<=N; j++) {
            for (int di=1; i+di<=N; di++) {
                for (int dj=1; j+dj<=N; dj++) {
                    R[di*dj] = max(
                            R[di*dj],
                            B[i+di][j+dj] - B[i][j+dj] - B[i+di][j] + B[i][j]
                        );
                }
            }
        }
    }
    int tmp = 0;
    for (int i=1; i<=N*N; i++) {
        if (tmp > R[i]) R[i] = tmp;
        else tmp = R[i];
    }

    int Q; cin >> Q;
    for (int i=0; i<Q; i++) {
        int P; cin >> P;
        cout << R[P] << endl;
    }
    return 0;
}

Submission Info

Judge Result