| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1342941 | ElayV13 | Toy (CEOI24_toy) | C++20 | 17 ms | 4144 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
int m,n,k,L;
int xh,yh,xv,yv;
char a[1501][1501];
int p[1501][1501];
bool used[1501][1501];
bool can[1501][1501];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool ok1[1501][1501];
bool ok2[1501][1501];
int get(int x1,int y1,int x2,int y2){
return p[x2][y2]-p[x2][y1-1]-p[x1-1][y2]+p[x1-1][y1-1];
}
pair<int,int> intersect(int x1,int y1,int x2,int y2){
return {x1,y2};
}
bool ok(int nwx,int nwy){
if(nwx<=n&&nwy<=m&&min(nwx,nwy)>=1&&ok1[nwx][nwy]&&ok2[nwx][nwy]&&a[nwx][nwy]!='X'&&!used[nwx][nwy]) return 1;
return 0;
}
void bfs(int x,int y){
queue<pair<int,int>>q;
q.push({x,y});
used[x][y]=1;
while(!q.empty()){
pair<int,int>v=q.front();
q.pop();
for(int i=0;i<4;i++){
int nwx=v.first+dx[i];
int nwy=v.second+dy[i];
if(ok(nwx,nwy)){
used[nwx][nwy]=1;
q.push({nwx,nwy});
}
}
}
}
void solve(){
cin>>m>>n>>k>>L;
cin>>xh>>yh>>xv>>yv;
++xh;
++yh;
++xv;
++yv;
swap(xh,yh);
swap(xv,yv);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+(a[i][j]=='X');
}
}
pair<int,int>point=intersect(xh,yh,xv,yv);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='X') continue;
int l=1,r=m-j+1,mx1=0,mx2=0;
while(l<=r){
int mid=(l+r)>>1;
if(!get(i,j,i,j+mid-1)){
mx1=max(mx1,mid);
l=mid+1;
}
else r=mid-1;
}
l=1,r=j;
while(l<=r){
int mid=(l+r)>>1;
if(!get(i,j-mid+1,i,j)){
mx2=max(mx2,mid);
l=mid+1;
}
else r=mid-1;
}
if(mx1+mx2-1>=L) ok1[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='X') continue;
int l=1,r=n-i+1,mx1=0,mx2=0;
while(l<=r){
int mid=(l+r)>>1;
if(!get(i,j,i+mid-1,j)){
mx1=max(mx1,mid);
l=mid+1;
}
else r=mid-1;
}
l=1,r=i;
while(l<=r){
int mid=(l+r)>>1;
if(!get(i-mid+1,j,i,j)){
mx2=max(mx2,mid);
l=mid+1;
}
else r=mid-1;
}
if(mx1+mx2-1>=k) ok2[i][j]=1;
}
}
bfs(point.first,point.second);
int xu=-1,yu=-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='*'){
xu=i;
yu=j;
}
}
}
cout<<((used[xu][yu])?"YES":"NO")<<endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;//cin>>T;
while(T--) solve();
}| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
