Submission #1964582

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <array>
#include <algorithm>
#include <cstdio>
#include <map>
#include <tuple>

using namespace std;

int N;

typedef tuple<int, int, int, int> tpl;

array<int, 30> X, Y;

map<tpl, int> mp;

// 左上 xl 左上 yt
// 右下 xr 右下 yb
int rect(int xl, int yt, int xr, int yb)
{
    tpl t = make_tuple(xl, yt, xr, yb);
    if (mp.count(t)) return mp[t];

    int ret = 0;
    for (int i = 0; i < N; i++)
    {
        int x = X[i];
        int y = Y[i];

        if (xl <= x && x <= xr && yt <= y && y <= yb)
        {
            int lt = rect(xl, yt, x - 1, y - 1);
            int rt = rect(x + 1, yt, xr, y - 1);
            int lb = rect(xl, y + 1, x - 1, yb);
            int ll = rect(x + 1, y + 1, xr, yb);
            ret = max(ret,(xr - xl) + (yb - yt) + 1 + lt + rt + lb + ll);
        }
    }

    mp[t] = ret;

    return ret;
}

int main()
{
    int W, H;
    if (scanf("%d%d%d", &W, &H, &N) < 2) return 0;

    for (int i = 0; i < N; i++)
    {
        if (scanf("%d%d", &X[i], &Y[i]) < 2) return 0;
    }

    printf("%d\n", rect(1, 1, W, H));
    return 0;
}

Submission Info

Judge Result