Submission #5900941

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define mod 1000000007
#define dom 998244353
#define all(c) begin(c),end(c)
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <typename T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }
#define long long long
#define List vector
#define var auto
#define Count size()
#define Length size()
int dd[] = { 0, 1, 0, -1, 0 }; //→↓←↑

using pi = pair<int, int>;
using pa = pair<pi, pi>;
vector<int> X;
vector<int> Y;
map<pa, long> dp;

long calc(int sy, int ty, int sx, int tx)
{
	if (ty <= sy || tx <= sx)return 0;
	if (dp.find(pa(pi(sy, ty), pi(sx, tx))) != dp.end())
	{
		return dp[pa(pi(sy, ty), pi(sx, tx))];
	}

	long ret = 0;
	int N = X.Length;
	rep(i, N)
	{
		if (sy <= Y[i] && Y[i] < ty && sx <= X[i] && X[i] < tx)
		{
			long sum = ty - sy + tx - sx - 1;
			sum += calc(sy, Y[i], sx, X[i]);
			sum += calc(sy, Y[i], X[i] + 1, tx);
			sum += calc(Y[i] + 1, ty, sx, X[i]);
			sum += calc(Y[i] + 1, ty, X[i] + 1, tx);

			ret = max(ret, sum);
		}
	}

	return dp[pa(pi(sy, ty), pi(sx, tx))] = ret;

}
void solve()
{
	int W, H, N;
	cin >> W >> H >> N;
	X = vector<int>(N);
	Y = vector<int>(N);
	rep(i, N)
	{
		cin >> X[i] >> Y[i];
		X[i]--;
		Y[i]--;
	}

	long ans = calc(0, H, 0, W);
	cout << ans << endl;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	return 0;
}

Submission Info

Judge Result