Submission #7098936

---

Source Code Expand

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

#define FOR(i, j, k) for (int i = j; i < k; i++)
#define REP(i, j) FOR(i, 0, j)
#define RFOR(i, k, j) for (int i = k - 1; i >= j; i--)
#define RREP(i, j) RFOR(i, j, 0)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T> istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec)
    is >> x;
  return is;
}

int dp[100][100][100][100];
vector<pii> xy;
int w, h, n;

int rec(int u, int l, int d, int r) {
  if (r - l <= 0 or u - d <= 0) return 0;
  if (dp[l][r][d][u] > 0) return dp[l][r][d][u];

  int ret = 0;
  for (auto& p: xy) {
    int x, y; tie(x, y) = p;
    int sum = 0;
    if (l <= x and x < r and d <= y and y < u) {
      sum = (r - l) + (u - d) - 1;
      sum += rec(y, l, d, x); // left down
      sum += rec(u, l, y + 1, x); // left up
      sum += rec(y, x + 1, d, r); // right down
      sum += rec(u, x + 1, y + 1, r); // right up
    }
    ret = max(ret, sum);
  }
  // cout << l << " " << r << " " << d << " " << u << " " << ret << endl;

  return dp[l][r][d][u] = ret;
}

int main() {

  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;

  cin >> w >> h >> n;

  REP(i, n) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    xy.emplace_back(x, y);
  }

  cout << rec(h, 0, 0, w) << endl;

  return 0;
}

Submission Info

Judge Result