link。
不是，怎么四方跑得飞快啊？成最优解了？有人会卡吗？鉴定为剪枝太多导致的。
一个出发点不太一样的思路。假设上下左右各被操作了 \(U,D,L,R\) 次。我们考虑一个点 \((x,y)\) 不被感染的条件是初始时 \([x-D,x+U]\times [y-R,y+L]\) 这个矩形内没有任何感染点。
考虑扣出所有中间没有感染点的极大矩形，极大矩形的定义是所有边界上要么挨着一个感染点要么是全局边界的矩形。这样的矩形至多只有 \(O(n^2)\) 种。为什么呢？考虑怎么扣出这些矩形，你枚举上边界顶到的点（或者是全局的上边界），然后对其严格下面所有点按 \(x\) 坐标建小根笛卡尔树，那么其 \(y\) 坐标所在的那一条链上每一个节点对应着一个极大矩形（如果是全局边界那么所有点都对应一个矩形）。自然有上界 \(O(n^2)\)。
同时这个过程也告诉我们四个边界包含至少一个全局边界的极大矩形是 \(O(n)\) 级别的。
考虑一个极大矩形对于 \(U,D,L,R\) 的限制，如果四面都是被感染点限制的，那么限制形如 \(U+D\le lenx\) 和 \(L+R\le leny\) 不能同时成立。但是如果有一面是全局边界，那么事实上这一面中矩形超过外边界是合法的，即限制可能变成了单独的 \(U/D\le lenx\) 或 \(L/R\le leny\) 的形式。
然后发现如果用 DS 维护这个东西有点 dirty，索性暴力枚举，即排序所有限制后暴力枚举 \(U,D,U+D\) 所在的限制区间，就推导出 \(L,R,L+R\) 分别的下界，取最小的 \(L+R\) 更新答案即可。
\(U,D\) 限制个数各 \(O(n)\) 种，\(U+D\) 限制个数可能达到 \(O(n^2)\)，所以理论复杂度 \(O(n^4)\)。但是出题人完全没卡极大矩形个数，所以这个做法表现跟平方差不多，结果十几毫秒断崖式最优解。
当然这个算法比较暴力，我觉得很有可能可以继续用 DS 优化。
#include <array>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=x*10+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
typedef long long ll;
const int N=303,T=200003;
const ll INF=0x3f3f3f3f3f3f3f3f;
typedef array<ll,3> arr;
typedef vector<int> vi;
int R,C,n,cur;ll res=INF;
int sx[N],sy[N];
arr X,Y;
inline void chmx(ll &x,ll v){if(x<v) x=v;}
inline void chmn(ll &x,ll v){if(x>v) x=v;}
struct node{
ll u,v;int d;
friend bool operator<(const node a,const node b){
return a.u<b.u;
}
}S[3][T];arr W;
inline int judgex(int xl,int xr){
if(xl==1&&xr==R) return -1;
if(xl==1) return 0;
if(xr==R) return 1;
return 2;
}
inline int judgey(int yl,int yr){
if(yl==1&&yr==C) return -1;
if(yl==1) return 0;
if(yr==C) return 1;
return 2;
}
void opt(int xl,int xr,int yl,int yr){
int lenx=xr-xl+1,leny=yr-yl+1;
int jx=judgex(xl,xr),jy=judgey(yl,yr);
if(jx<0) return chmx(Y[jy],leny);
if(jy<0) return chmx(X[jx],lenx);
S[jx][W[jx]++]=(node){lenx,leny,jy};
}
void solve(int l,int r,vi vc,int las){
if(vc.empty()) return opt(sx[cur]+1,R,l,r);
int mn=vc.front();
for(int x:vc) if(sx[x]<sx[mn]) mn=x;
if(sx[cur]<sx[mn]-1&&sx[mn]>las) opt(sx[cur]+1,sx[mn]-1,l,r);
if((!cur||sy[cur]<sy[mn])&&l<sy[mn]){
vi tmp;
for(int x:vc) if(sy[x]<sy[mn]) tmp.emplace_back(x);
solve(l,sy[mn]-1,tmp,sx[mn]);
}
if((!cur||sy[cur]>sy[mn])&&sy[mn]<r){
vi tmp;
for(int x:vc) if(sy[x]>sy[mn]) tmp.emplace_back(x);
solve(sy[mn]+1,r,tmp,sx[mn]);
}
}
int main(){
R=read();C=read();n=read();
for(int i=1;i<=n;++i) sx[i]=read(),sy[i]=read();
vi init;
for(int i=1;i<=n;++i){
if(sx[i]==R) continue;
for(int j=1;j<=n;++j)
if(sx[j]>sx[i]) init.emplace_back(j);
cur=i;solve(1,C,init,0);init.clear();
}
for(int i=1;i<=n;++i) init.emplace_back(i);
cur=0;solve(1,C,init,0);
for(int t=0;t<3;++t) sort(S[t],S[t]+W[t]),S[t][W[t]].u=INF;
arr Yi=Y;
for(int i=W[0];~i;--i){
if(i<W[0]) chmx(Yi[S[0][i].d],S[0][i].v);
ll l0=X[0],r0=S[0][i].u-1;
if(l0>r0) break;
if(i) chmx(l0,S[0][i-1].u);
if(l0>r0) continue;
arr Yj=Yi;
for(int j=W[1];~j;--j){
if(j<W[1]) chmx(Yj[S[1][j].d],S[1][j].v);
ll l1=X[1],r1=S[1][j].u-1;
if(l1>r1) break;
if(j) chmx(l1,S[1][j-1].u);
if(l1>r1) continue;
arr Yk=Yj;
for(int k=W[2];~k;--k){
if(k<W[2]) chmx(Yk[S[2][k].d],S[2][k].v);
ll l2=X[2],r2=S[2][k].u-1;
if(l2>r2) break;
if(k) chmx(l2,S[2][k-1].u);
if(l2>r2||l2>r0+r1) continue;
if(r2<l0+l1) break;
chmn(res,max(Yk[0]+Yk[1],Yk[2])+max(l0+l1,l2));
}
}
}
printf("%lld\n",res);
return 0;
}