C++11(clang++ 3.9) 解法, 执行用时: 1546ms, 内存消耗: 2804K, 提交时间: 2019-10-24 09:51:42

#include <bits/stdc++.h>
#define templated template <typename T>
#define EB emplace_back

typedef unsigned int u32;
typedef std::pair <int, int> pr;
typedef std::pair <u32, int> upr;
typedef std::tuple <int, int, int> tup;
typedef std::vector <int> vector;
const int N = 354, M = 654, INF = 0x7f7f7f7f;

int R, C, n;
vector prob, hi;
pr a[N];
tup hor[N][N], b[M];

templated inline bool up(T &x, const T y) {return x < y ? x = y, 1 : 0;}
templated inline bool down(T &x, const T y) {return x > y ? x = y, 1 : 0;}
inline u32 max(const u32 x, const u32 y) {return x < y ? y : x;}

struct monoqueue {
	int n, h, t;
	pr *que;
	monoqueue () : n(0), h(0), t(0), que(NULL) {}
	~monoqueue () {if (que) delete [] (que);}
	void resize(int _n) {if (que) delete [] (que); n = _n, h = t = 0, que = new pr[n + 1];}
	inline void clear() {h = t = 0;}
	void push(int key, int val) {for (; h < t && que[t - 1].second <= val; --t); que[t++] = pr(key, val);}
	int get(int key) {for (; h < t && que[h].first < key; ++h); return que[h].second;}
} LQ, RQ, MQ;

namespace DC {
	int F[M]; upr D[M];

	int Discretize(int n) {
		int i, cnt = 0; std::inplace_merge(D, D + n, D + n * 2);
		for (i = 0; i < n * 2; ++i) F[D[i].second] = (i && D[i].first == D[i - 1].first ? cnt - 1 : (D[cnt] = D[i], cnt++));
		return cnt;
	}
}

void init_horizontal() {
	int i, j, la, L, R, M;
	for (i = 0; i < n; ++i)
		for (hi.clear(), j = i; j < n; ++j) {
			hi.insert(std::lower_bound(hi.begin(), hi.end(), a[j].second), a[j].second);
			la = L = hi.front() - 1, R = C - hi.back(), M = 0;
			for (int c : hi) up(M, c - la - 1), la = c;
			hor[i][j] = tup(L, R, M);
		}
}

int work(int step, int ans) {
	int i, l, r, cnt = 0, Lv, Rv, Mv; u32 ret = INF;
	for (i = 0; i < n; ++i)
		DC::D[i] = upr(a[i].first, i), DC::D[i + n] = upr(a[i].first + step + 1, i + n);
	cnt = DC::Discretize(n);
	for (l = r = i = 0; i < cnt - 1; ++i) {
		for (; l < n && DC::F[l + n] <= i; ++l);
		for (; r < n && DC::F[r] <= i; ++r);
		if (l >= r) return INF;
		b[i] = hor[l][r - 1];
	}
	LQ.clear(), RQ.clear(), MQ.clear();
	for (r = 0; r < cnt - 1 && DC::D[r].first < DC::D->first + R; ++r)
		std::tie(Lv, Rv, Mv) = b[r], LQ.push(r, Lv), RQ.push(r, Rv), MQ.push(r, Mv);
	for (l = 0; r < cnt; ++r) {
		for (up(l, 0); l <= r && DC::D[l].first + R <= DC::D[r].first; ++l);
		if (l--) down<u32>(ret, max(LQ.get(l) + RQ.get(l), MQ.get(l)));
		if (r < cnt) std::tie(Lv, Rv, Mv) = b[r], LQ.push(r, Lv), RQ.push(r, Rv), MQ.push(r, Mv);
	}
	return ret;
}

int main() {
	int i, j, limit; u32 ans;
	scanf("%d%d%d", &R, &C, &n), ans = R + C - 2;
	for (i = 0; i < n; ++i) scanf("%d%d", &a[i].first, &a[i].second);
	std::sort(a, a + n), init_horizontal();
	for (prob.EB(0), i = 0; i < n; ++i) {
		prob.EB(a[i].first - 1), prob.EB(R - a[i].first);
		for (j = 0; j < n; ++j)
			prob.EB(a[j].first - a[i].first - 1), prob.EB((a[i].first - 1) + (R - a[j].first));
	}	
	std::sort(prob.begin(), prob.end()), prob.erase(std::unique(prob.begin(), prob.end()), prob.end());
	LQ.resize(n * 2), RQ.resize(n * 2), MQ.resize(n * 2);
	limit = (a->first - 1) + (R - a[n - 1].first);
	for (int l : prob) if (limit <= l && (u32)l <= ans) down<u32>(ans, l + work(l, ans));
	printf("%u\n", ans);
	return 0;
}