Submission #1233600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233600		sophiaeternalia	Toy (CEOI24_toy)	C++20	100 / 100	127 ms	47052 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    cin.tie(0); ios_base::sync_with_stdio(NULL);

    int w, h, k, l, xh, yh, xv, yv;
    cin>>w>>h>>k>>l>>xh>>yh>>xv>>yv;
    int xx=xv, yy=yh;
    vector<string> g(h);
    for (int i=0; i<h; i++){
        cin>>g[i];
    }
    vector<vector<array<int, 4>>> t(w, vector<array<int, 4>> (h, {-1, h, -1, w}));
    for (int i=0; i<w; i++){
        int a=-1;
        for (int j=0; j<h; j++){
            if (g[j][i]=='X'){
                a=j;
            }
            t[i][j][0]=a;
        }
        a=h;
        for (int j=h-1; j>=0; j--){
            if (g[j][i]=='X'){
                a=j;
            }
            t[i][j][1]=a;
        }
    }
    for (int i=0; i<h; i++){
        int a=-1;
        for (int j=0; j<w; j++){
            if (g[i][j]=='X'){
                a=j;
            }
            t[j][i][2]=a;
        }
        a=w;
        for (int j=w-1; j>=0; j--){
            if (g[i][j]=='X'){
                a=j;
            }
            t[j][i][3]=a;
        }
    }
    vector<vector<int>> vi(w, vector<int> (h, 0));
    queue<pair<int, int>> q;
    q.push({xx, yy});
    while (!q.empty()){
        int x=q.front().first, y=q.front().second;
        q.pop();
        if (g[y][x]=='*'){
            cout<<"YES"<<"\n";
            return 0;
        }
        if (vi[x][y]==1){
            continue;
        }
        vi[x][y]=1;
        if (t[x][y][0]!=y-1 and min(t[x][y-1][3], t[x][y][3])-max(t[x][y-1][2], t[x][y][2])-1>=k){
            q.push({x, y-1});
        }
        if (t[x][y][1]!=y+1 and min(t[x][y+1][3], t[x][y][3])-max(t[x][y+1][2], t[x][y][2])-1>=k){
            q.push({x, y+1});
        }
        if (t[x][y][2]!=x-1 and min(t[x-1][y][1], t[x][y][1])-max(t[x-1][y][0], t[x][y][0])-1>=l){
            q.push({x-1, y});
        }
        if (t[x][y][3]!=x+1 and min(t[x+1][y][1], t[x][y][1])-max(t[x+1][y][0], t[x][y][0])-1>=l){
            q.push({x+1, y});
        }
    }
    cout<<"NO"<<"\n";
}

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