Submission #1140737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140737		Faisal_Saqib	Toy (CEOI24_toy)	C++17	73 / 100	1598 ms	93512 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

const int N=3000;
char grid[N][N];
int pre_row[N][N],pre_col[N][N],U_max[N][N],U_min[N][N],L_max[N][N],L_min[N][N];
bool seen[N][N];
int k,l,h,w;
int get_row(int x,int y)
{
	return pre_row[x][y+k]-pre_row[x][y];
}
int get_col(int x,int y)
{
	return pre_col[x+l][y]-pre_col[x][y];
}
queue<pair<int,int>> q;
bool intersection(int x1,int y1,int x2,int y2)
{
	return max(x1,x2)<=min(y1,y2);
}
int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin>>w>>h>>k>>l;
	int xh1,yh1,xv1,yv1;
	cin>>xh1>>yh1>>xv1>>yv1;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			cin>>grid[i][j];
			pre_row[i][j+1]=pre_row[i][j]+(grid[i][j]=='X');
			pre_col[i+1][j]=pre_col[i][j]+(grid[i][j]=='X');
		}
	}
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			U_max[i][j]=L_max[i][j]=-1e9;
			U_min[i][j]=L_min[i][j]=1e9;
		}
	}
	// O(N^4) --> O(N^3) done
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			for(int U=0;U<=min(l-1,i);U++)
			{
				int D=l-1-U;
				if(D<0)
				{
					exit(-1);
				}
				if(D<0 or (i+D)>=h)continue;
				if(get_col(i-U,j)==0)
				{
					U_min[i][j]=min(U_min[i][j],U);
					U_max[i][j]=max(U_max[i][j],U);
				}
			}
			for(int L=0;L<=min(j,k-1);L++)
			{
				int R=k-1-L;
				if(R<0)
				{
					exit(-1);
				}
				if(R<0 or (j+R)>=w)continue;

				if(get_row(i,j-L)==0)
				{
					L_min[i][j]=min(L_min[i][j],L);
					L_max[i][j]=max(L_max[i][j],L);
				}
			}
		}
	}
	vector<pair<int,int>> dir={{-1,0},{0,-1},{0,1},{1,0}};
	q.push({yh1,xv1});
	seen[yh1][xv1]=1;
	int tp=0,x,y,y1,x1;
	while(q.size()>0)
	{
		auto it=q.front();
		q.pop();
		if(grid[it.ff][it.ss]=='*')
		{
			cout<<"YES"<<endl;
			return 0;
		}
		x=it.ff,y=it.ss;
		for(auto&[dx,dy]:dir)
		{
			it.ff+=dx;
			it.ss+=dy;
			x1=it.ff;
			y1=it.ss;
			if(min(x1,y1)>=0 and x1<h and y1<w and !seen[x1][y1])
			{
				if(intersection(x-U_max[x][y],x-U_min[x][y],x1-U_max[x1][y1],x1-U_min[x1][y1]) and intersection(y-L_max[x][y],y-L_min[x][y],y1-L_max[x1][y1],y1-L_min[x1][y1]))
				{
					q.push({x1,y1});
					seen[x1][y1]=1;
				}
			}
			it.ff-=dx;
			it.ss-=dy;
		}
	}
	cout<<"NO"<<endl;
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 0 / 27