Submission #1346042

#TimeUsernameProblemLanguageResultExecution timeMemory
1346042cpismayilmmdv985Toy (CEOI24_toy)C++20
0 / 100
56 ms5260 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]; 

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];
}

bool is_covered(int r, int c, int r_int, int c_int, int yh, int xv) {
    bool on_h = (r == r_int && c >= yh && c < yh + K);
    bool on_v = (c == c_int && r >= xv && r < xv + L);
    return on_h || on_v;
}

void solve() {
    cin >> W >> H >> K >> L;
    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++) {
        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\n"; 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) continue;
            int new_L = MAX, new_R = -1;
            int min_possible_yh = max(0, nc - K + 1);
            int max_possible_yh = min(W - K, nc);
            for (int yh = min_possible_yh; yh <= max_possible_yh; yh++) {
                if (get_sum(nr, yh, nr, yh + K - 1) > 0) continue;
                int xv = max(0, nr - L + 1); 
                bool ok_v = false;
                for(int cur_xv = max(0, nr-L+1); cur_xv <= min(H-L, nr); cur_xv++) {
                    if (get_sum(cur_xv, nc, cur_xv + L - 1, nc) == 0) {
                        if (abs(yh - cur_L) <= 1 || abs(yh - cur_R) <= 1 || (yh >= cur_L && yh <= cur_R)) {
                            new_L = min(new_L, yh);
                            new_R = max(new_R, yh);
                        }
                    }
                }
            }
            if (new_L <= new_R) {
                if (new_L < L_yh[nr][nc] || new_R > R_yh[nr][nc]) {
                    L_yh[nr][nc] = min(L_yh[nr][nc], new_L);
                    R_yh[nr][nc] = max(R_yh[nr][nc], new_R);
                    q.push({nr, nc});
                }
            }
        }
    }
    cout << "NO\n";
}

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...