Submission #7146272

---

Source Code Expand

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

int main(){
    int w, h;
    cin >> w >> h;
    int n;
    cin >> n;
    vector<pair<int, int>> gold(n);
    vector<int> dx;
    vector<int> dy;
    map<int, bool> used_x;
    map<int, bool> used_y;
    dx.push_back(0);
    used_x[0] = true;
    dx.push_back(w - 1);
    used_x[w - 1] = true;
    dy.push_back(0);
    used_y[0] = true;
    dy.push_back(h - 1);
    used_y[h - 1] = true;
    for (int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        x--; y--;
        gold[i] = {x, y};
        if (x != 0 && !used_x[x - 1]) {
            dx.push_back(x - 1);
            used_x[x - 1] = true;
        }
        if (x != w - 1 && !used_x[x + 1]) {
            dx.push_back(x + 1);
            used_x[x + 1] = true;
        }
        if (y != 0 && !used_y[y - 1]) {
            dy.push_back(y - 1);
            used_y[y - 1] = true;
        }
        if (y != h - 1 && !used_y[y + 1]) {
            dy.push_back(y + 1);
            used_y[y + 1] = true;
        }
    }
    sort(dx.begin(), dx.end());
    sort(dy.begin(), dy.end());
    map<int, int> xpos;
    map<int, int> ypos;
    int p = dx.size();
    int q = dy.size();
    for (int i = 0; i < p; i++) xpos[dx[i]] = i;
    xpos[- 1] = - 1; xpos[w] = p;
    for (int i = 0; i < q; i++) ypos[dy[i]] = i;
    ypos[- 1] = - 1; ypos[h] = q;
    vector<vector<vector<vector<long long>>>> dp(p, vector<vector<vector<long long>>>(q, vector<vector<long long>>(p, vector<long long>(q, 0))));
    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq;
    for (int i = 0; i < p; i++){
        for (int j = 0; j < q; j++){
            for (int s = i; s < p; s++){
                for (int t = j; t < q; t++){
                    long long fac = (dx[s] - dx[i] + 1) * (dy[t] - dy[j] + 1);
                    int a = i * 100 + j;
                    int b = s * 100 + t;
                    pq.push(tie(fac, a, b));
                }
            }
        }
    }
    while (pq.size()){
        long long fac;
        int a, b;
        tie(fac, a, b) = pq.top();
        pq.pop();
        int ux, uy, sx, sy;
        ux = a / 100;
        uy = a % 100;
        sx = b / 100;
        sy = b % 100;
        bool flag = true;
        for (int i = 0; i < n; i++){
            if (gold[i].first < dx[ux] || gold[i].first > dx[sx] || gold[i].second < dy[uy] || gold[i].second > dy[sy]) continue;
            long long d1, d2, d3, d4;
            d1 = 0; d2 = 0; d3 = 0; d4 = 0;
            if (ux <= xpos[gold[i].first - 1] && uy <= ypos[gold[i].second - 1]) d1 = dp[ux][uy][xpos[gold[i].first - 1]][ypos[gold[i].second - 1]];
            if (xpos[gold[i].first + 1] <= sx && uy <= ypos[gold[i].second - 1]) d2 = dp[xpos[gold[i].first + 1]][uy][sx][ypos[gold[i].second - 1]];
            if (ux <= xpos[gold[i].first - 1] && ypos[gold[i].second + 1] <= sy) d3 = dp[ux][ypos[gold[i].second + 1]][xpos[gold[i].first - 1]][sy];
            if (xpos[gold[i].first + 1] <= sx && ypos[gold[i].second + 1] <= sy) d4 = dp[xpos[gold[i].first + 1]][ypos[gold[i].second + 1]][sx][sy];
            dp[ux][uy][sx][sy] = max(dp[ux][uy][sx][sy], dx[sx] - dx[ux] + dy[sy] - dy[uy] + 1 + d1 + d2 + d3 + d4);
        }
    }
    cout << dp[0][0][p - 1][q - 1] << endl;
}

Submission Info

Judge Result