ABC D题神秘RE求救
  • 板块学术版
  • 楼主ShanQing
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/3/16 21:40
  • 上次更新2024/3/16 21:46:23
查看原帖
ABC D题神秘RE求救
368204
ShanQing楼主2024/3/16 21:40

本地+洛谷IDE跑样例都没问题,同时程序加了各种剪枝也跑的飞快,结果提交显示样例RE,其它也大多都是RE。

从来没遇到过。喜提罚坐。

//writer:Oier_szc

#include <bits/stdc++.h>
//#include <windows.h>
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define int long long
using namespace std;
const int N=100,INF=2e9,mod=1e9+7;
int n,ans=0;
int h,w;
struct node
{
	int h,w;
	bool operator<(const node &W) const
	{
		return h*w>W.h*W.w;
	}
}a[N];
int qwq[N];
int b[N][N],qzh[N][N],cnt=0;
bool in(int x,int y)
{
	return x>=1&&x<=h&&y>=1&&y<=w;
}
bool fg(int x,int y,int H,int W)
{
	if(!in(x+H-1,y+W-1)) return false;
	if(qzh[x+H-1][y+W-1]-qzh[x-1][y+W-1]-qzh[x+H-1][y-1]+qzh[x-1][y-1]!=0) return false;
	for(int i=x;i<=x+H-1;++i)
	{
		for(int j=y;j<=y+W-1;++j) b[i][j]=1,++cnt;
	}
	for(int i=1;i<=h;++i)
	{
		for(int j=1;j<=w;++j) qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+b[i][j];
	}
}
void clear(int x,int y,int H,int W)
{
	for(int i=x;i<=x+H-1;++i)
	{
		for(int j=y;j<=y+W-1;++j) b[i][j]=0,--cnt;
	}
	for(int i=1;i<=h;++i)
	{
		for(int j=1;j<=w;++j) qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+b[i][j];
	}
}
bool dfs(int id)
{
	if(id==n+1) 
	{
		return cnt==h*w;
	}
	if(cnt+qwq[id]<h*w) return false;
	if(dfs(id+1)) return true;
	if(cnt+a[id].h*a[id].w<=h*w)
	{
		for(int i=1;i<=h;++i)
		{
			for(int j=1;j<=w;++j)
			{
				if(b[i][j]) continue;
				if(fg(i,j,a[id].h,a[id].w))
				{
					if(dfs(id+1)) return true;
					clear(i,j,a[id].h,a[id].w);
				}
				if(fg(i,j,a[id].w,a[id].h))
				{
					if(dfs(id+1)) return true;
					clear(i,j,a[id].w,a[id].h);
				}
			}
		}
	}
	return false;
}
signed main()
{
	scanf("%lld%lld%lld",&n,&h,&w);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld",&a[i].h,&a[i].w);
	}
	qwq[n+1]=0;
	for(int i=n;i>=1;--i) qwq[i]=qwq[i+1]+a[i].h*a[i].w;
	sort(a+1,a+1+n);
	printf(dfs(1)?"Yes\n":"No\n");
	return 0;
}
/*

*/
2024/3/16 21:40
加载中...