Submission #1140507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140507		SyedSohaib_123	Toy (CEOI24_toy)	C++20	0 / 100	3 ms	2632 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define append push_back
#define int long long

const int N=4e5+10,LG=17;
int mod=998244353;

void solve(int tst){
    int n,m,k,l;
    cin>>n>>m>>k>>l;
    swap(n,m);
    int a,b,c,D;
    cin>>b>>a>>D>>c;
    a++;b++;
    c++;D++;
    int x=a,y=D;
    vector<string>v(n+2,string(m+2,'X'));
    for(int i=1;i<=n;i++){
        cin>>v[i];
        v[i]="X"+v[i]+"X";
    }
    vector<vector<int>>dx(n+2,vector<int>(m+2)),dy=dx,ps=dx;
    for(int i=0;i<=n+1;i++){
        vector<int>t(m+2,0);
        int l=0;
        for(int j=0;j<=m+1;j++){
            if(v[i][j]=='X') l=j;
            t[j]=l;
        }
        l=m+1;
        for(int j=m+1;j+1;j--){
            if(v[i][j]=='X') l=j;
            dx[i][j]=l-t[j]-1;
        }
    }
    for(int i=0;i<=m+1;i++){
        vector<int>t(n+2,0);
        int l=0;
        for(int j=0;j<=n+1;j++){
            if(v[j][i]=='X') l=j;
            t[j]=l;
        }
        l=n+1;
        for(int j=n+1;j+1;j--){
            if(v[j][i]=='X') l=j;
            dy[j][i]=l-t[j]-1;
        }
    }
    // K -> j
    ps[x][y]=1;
    deque<pair<int,int>>d;
    d.append({x,y});
    while(d.size()){
        auto [X,Y]=d[0];
        d.pop_front();
        if(v[X-1][Y]!='X' and !ps[X-1][Y] and dy[X-1][Y]>=l and dx[X-1][Y]>=k){
            ps[X-1][Y]=1;
            d.append({X-1,Y});
        }
        if(v[X+1][Y]!='X' and !ps[X+1][Y] and dy[X+1][Y]>=l and dx[X+1][Y]>=k){
            ps[X+1][Y]=1;
            d.append({X+1,Y});
        }
        if(v[X][Y-1]!='X' and !ps[X][Y-1] and dy[X][Y-1]>=l and dx[X][Y-1]>=k){
            ps[X][Y-1]=1;
            d.append({X,Y-1});
        }
        if(v[X][Y+1]!='X' and !ps[X][Y+1] and dy[X][Y+1]>=l and dx[X][Y+1]>=k){
            ps[X][Y+1]=1;
            d.append({X,Y+1});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ps[i][j] and v[i][j]=='*'){
                cout<<"YES"<<endl;return;
            }
        }
    }
    cout<<"NO"<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve(i);
    }
}

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