Submission #6021020

---

Source Code Expand

void solve();

int main() {
	solve();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>

using namespace std;

int W,H,N;
typedef pair<int, int> pii;
vector<pii> POS;
vector<int> X, Y;
vector<vector<int>> MAP;
vector<vector<int>> XSUM, YSUM;   //XSUM[x][y] = Σ1<=i<=x MAP[i][y]
int DP[62][62][62][62];

void solve() {
	cin >>W >> H >> N;
	POS.resize(N);
	for (int n = 0; n < N; n++) {
		int x, y;
		cin >> x >> y;
		POS[n] = pii(x, y);
	}
	POS.push_back(pii(W + 1, H + 1));
	sort(POS.begin(), POS.end(), [](pii a, pii b) {return a.first < b.first; });
	X.push_back(0);
	if(POS[0].first != 1)X.push_back(1);
	for (int n = 1; n <= N; n++) {
		if (POS[n].first != POS[n - 1].first) {
			X.push_back(POS[n - 1].first);
			if (POS[n].first - POS[n - 1].first > 1)X.push_back(POS[n - 1].first + 1);
		}
	}
	sort(POS.begin(), POS.end(), [](pii a, pii b) {return a.second < b.second; });
	Y.push_back(0);
	if (POS[0].second != 1)Y.push_back(1);
	for (int n = 1; n <= N; n++) {
		if (POS[n].second != POS[n - 1].second) {
			Y.push_back(POS[n - 1].second);
			if (POS[n].second - POS[n - 1].second > 1)Y.push_back(POS[n - 1].second + 1);
		}
	}
	X.push_back(W + 1); Y.push_back(H + 1);
	MAP.resize(X.size());
	for (int x = 0; x < X.size(); x++)MAP[x].resize(Y.size(),0);
	for (int xn = 1; xn < X.size() - 1; xn++) {
		for (int yn = 1; yn < Y.size() - 1; yn++) {
			MAP[xn][yn] = (X[xn + 1] - X[xn]) * (Y[yn + 1] - Y[yn]);
		}
	}
	XSUM.resize(X.size()-1);
	YSUM.resize(X.size() - 1);
	for (int x = 0; x < X.size()-1; x++) {
		XSUM[x].resize(Y.size() - 1, 0);
		YSUM[x].resize(Y.size() - 1, 0);
	}

	for (int x = 1; x < X.size()-1; x++) {
		for (int y = 1; y < Y.size()-1; y++) {
			XSUM[x][y] = XSUM[x - 1][y] + MAP[x][y];
			YSUM[x][y] = YSUM[x][y - 1] + MAP[x][y];
		}
	}
	sort(POS.begin(), POS.end(), [](pii a, pii b) {return a.first < b.first; });
	for (int n = 1; n <= N; n++) {
		int oldx = POS[n].first;
		POS[n].first = POS[n - 1].first;
		while (X[POS[n].first] != oldx)POS[n].first++;
	}
	sort(POS.begin(), POS.end(), [](pii a, pii b) {return a.second < b.second; });
	for (int n = 1; n <= N; n++) {
		int oldy = POS[n].second;
		POS[n].second = POS[n - 1].second;
		while (Y[POS[n].second] != oldy)POS[n].second++;
	}
	for (int x1 = 0; x1 < X.size() - 1; x1++) {
		for (int x2 = 0; x2 < X.size() - 1; x2++) {
			for (int y1 = 0; y1 < Y.size() - 1; y1++) {
				for (int y2 = 0; y2 < Y.size() - 1; y2++) {
					DP[x1][x2][y1][y2] = 0;
				}
			}
		}
	}
	for (int w = 0; w < X.size()-1; w++) {
		for (int x1 = 1; x1 + w < X.size() - 1; x1++) {
			for (int h = 0; h < Y.size()-1; h++) {
				for (int y1 = 1; y1 + h < Y.size()-1; y1++) {
					int x2 = x1 + w, y2 = y1 + h;
					for (int n = 0; n < N; n++) {
						if (POS[n].first < x1 || POS[n].first > x2 ||
							POS[n].second < y1 || POS[n].second > y2)continue;
						int xsum = XSUM[x2][POS[n].second] - XSUM[x1 - 1][POS[n].second];
						int ysum = YSUM[POS[n].first][y2] - YSUM[POS[n].first][y1 - 1];
						int sum = xsum + ysum - MAP[POS[n].first][POS[n].second];
						DP[x1][x2][y1][y2] = max(DP[x1][x2][y1][y2],
							sum + DP[x1][POS[n].first - 1][y1][POS[n].second - 1]
							+ DP[POS[n].first + 1][x2][y1][POS[n].second - 1]
							+ DP[x1][POS[n].first - 1][POS[n].second + 1][y2]
							+ DP[POS[n].first + 1][x2][POS[n].second + 1][y2]);
					}
				}
			}
		}
	}
	cout << DP[1][X.size() - 2][1][Y.size() - 2] << endl;
	return;
}

Submission Info

Judge Result