Submission #1346043

#TimeUsernameProblemLanguageResultExecution timeMemory
1346043cpismayilmmdv985Toy (CEOI24_toy)C++20
0 / 100
6 ms8348 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1505;
int W, H, K, L;
string grid[MAX];
int pref[MAX][MAX];
int L_yh[MAX][MAX], R_yh[MAX][MAX];
int h_lim_L[MAX][MAX], h_lim_R[MAX][MAX];

inline int get_sum(int r1, int c1, int r2, int c2) {
    if (r1 < 0 || r2 >= H || c1 < 0 || c2 >= W) return 1e9;
    return pref[r2 + 1][c2 + 1] - pref[r1][c2 + 1] - pref[r2 + 1][c1] + pref[r1][c1];
}

void solve() {
    if (!(cin >> W >> H >> K >> L)) return;
    int cH, rH, cV, rV;
    cin >> cH >> rH >> cV >> rV;

    for (int i = 0; i < H; i++) {
        cin >> grid[i];
        for (int j = 0; j < W; j++)
            pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + (grid[i][j] == 'X');
    }

    for (int i = 0; i < H; i++) {
        int last = -1;
        for (int j = 0; j <= W - K; j++) {
            if (get_sum(i, j, i, j + K - 1) == 0) {
                if (last == -1) last = j;
                h_lim_L[i][j] = last;
            } else last = -1;
        }
        last = -1;
        for (int j = W - K; j >= 0; j--) {
            if (get_sum(i, j, i, j + K - 1) == 0) {
                if (last == -1) last = j;
                h_lim_R[i][j] = last;
            } else last = -1;
        }
    }

    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            L_yh[i][j] = MAX; R_yh[i][j] = -1;
        }
    }

    queue<pair<int, int>> q;
    L_yh[rH][cV] = R_yh[rH][cV] = cH;
    q.push({rH, cV});

    int dr[] = {0, 0, 1, -1};
    int dc[] = {1, -1, 0, 0};

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        if (grid[r][c] == '*') { cout << "YES" << endl; return; }

        int cur_l = L_yh[r][c], cur_r = R_yh[r][c];

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr < 0 || nr >= H || nc < 0 || nc >= W || grid[nr][nc] == 'X') continue;

            bool can_v = false;
            for(int xv = max(0, nr-L+1); xv <= min(H-L, nr); xv++) {
                if(get_sum(xv, nc, xv + L - 1, nc) == 0) {
                    can_v = true; break;
                }
            }
            if(!can_v) continue;

            int nL = max(nc - K + 1, cur_l);
            int nR = min(nc, cur_r);

            if (nL <= nR || (abs(nc - c) <= 1 && abs(nr - r) <= 1)) {
                int possible_L = max(0, nc - K + 1);
                int possible_R = min(W - K, nc);
                
                int real_L = h_lim_L[nr][possible_L];
                int real_R = h_lim_R[nr][possible_R];

                if (real_L < L_yh[nr][nc] || real_R > R_yh[nr][nc]) {
                    L_yh[nr][nc] = min(L_yh[nr][nc], real_L);
                    R_yh[nr][nc] = max(R_yh[nr][nc], real_R);
                    q.push({nr, nc});
                }
            }
        }
    }
    cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    solve();
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...