求助,Subtask #2#3 WA
查看原帖
求助,Subtask #2#3 WA
881015
Resstifnurvˆwˆ.tar.gz楼主2023/12/30 09:08
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

inline int read(){
	int ret=0;
	char ch=' ',c=getchar();
	while(!('0'<=c&&c<='9')) ch=c,c=getchar();
	while('0'<=c&&c<='9') ret=(ret<<1)+(ret<<3)+(c^48),c=getchar();
	return ch=='-'?-ret:ret;
}

int n,m,k;
ll ans=0;

set<pii> tbl;
bool ok(int x,int y){
	if(tbl.find(make_pair(x,y))!=tbl.end()) return false;
	else return true;
}

vector<int> sx,sy;
vector<ll> sumx,sumy;
ll calc(int x,int y){
	ll ans=0;
	int l=0,r=k+1,mid;
	while(l<r){
		mid=(l+r+1)>>1;
		if(sx[mid]<=x) l=mid;
		else r=mid-1;
	}
	if(l==k+1) ans+=k*x-sumx[k];
	else{
		ans+=l*x-sumx[l];
		ans+=sumx[k]-sumx[l]-(k-l)*x;
	}
	l=0,r=k+1;
	while(l<r){
		mid=(l+r+1)>>1;
		if(sy[mid]<=y) l=mid;
		else r=mid-1;
	}
	if(l==k+1) ans+=k*y-sumy[k];
	else{
		ans+=l*y-sumy[l];
		ans+=sumy[k]-sumy[l]-(k-l)*y;
	}
	return ans;
}

int dx[]={+1,0,-1,0};
int dy[]={0,+1,0,-1};

set<pii> vis;
bool vs(int x,int y){
	if(vis.find(make_pair(x,y))!=vis.end()) return false;
	else return true;
}

void dfs(int x,int y){
	if(ok(x,y)){
		ll tmp=calc(x,y);
//		printf("(%d,%d)=%lld\n",x,y,tmp);
		ans=max(ans,tmp);
		return ;
	}
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx<=0||xx>n||yy<=0||yy>m) continue;
		if(vs(xx,yy)){
			vis.insert(make_pair(xx,yy));
			dfs(xx,yy);
		}
	}
}

int main(){
	n=read(),m=read(),k=read();
	int x,y;
	for(int i=1;i<=k;i++){
		x=read(),y=read();
		tbl.insert(make_pair(x,y));
		sx.push_back(x);
		sy.push_back(y);
	}
	sx.push_back(0);
	sy.push_back(0);
	sx.push_back(0x3f3f3f3f);
	sy.push_back(0x3f3f3f3f);
	sort(sx.begin(),sx.end());
	sort(sy.begin(),sy.end());
	int t=0;
	for(int i=0;i<=k;i++){
		t+=sx[i];
		sumx.push_back(t);
	}
	t=0;
	for(int i=0;i<=k;i++){
		t+=sy[i];
		sumy.push_back(t);
	}
	dfs(1,1);
	dfs(1,m);
	dfs(n,1);
	dfs(n,m);
	printf("%lld",ans);
	return 0;
}
2023/12/30 09:08
加载中...