Submission #1260378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260378		antonn	Toy (CEOI24_toy)	C++20	100 / 100	134 ms	40452 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1500 + 7;

int w, h, k, l, xh, yh, xv, yv;
string s[N];
int lft[N][N], rgh[N][N], up[N][N], down[N][N];
bool vis[N][N];

int inter(int lx, int rx, int ly, int ry) {
    return max(0, min(rx, ry) - max(lx, ly) - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> w >> h >> k >> l >> yh >> xh >> yv >> xv;
    ++xh, ++yh, ++xv, ++yv;
    for (int i = 1; i <= h; ++i) cin >> s[i], s[i] = "#" + s[i];
    int xf, yf;
    for (int i = 1; i <= h; ++i) for (int j = 1; j <= w; ++j) if (s[i][j] == '*') xf = i, yf = j;
    
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            lft[i][j] = lft[i][j - 1];
            up[i][j] = up[i - 1][j];
            if (s[i][j] == 'X') lft[i][j] = j, up[i][j] = i;
        }
    }
    for (int i = 1; i <= h + 1; ++i) {
        for (int j = 1; j <= w + 1; ++j) {
            rgh[i][j] = w + 1;
            down[i][j] = h + 1;
        }
    }
    for (int i = h; i >= 1; --i) {
        for (int j = w; j >= 1; --j) {
            rgh[i][j] = rgh[i][j + 1];
            down[i][j] = down[i + 1][j];
            if (s[i][j] == 'X') rgh[i][j] = j, down[i][j] = i;
        }
    }
    
    queue<pair<int, int>> q;
    q.push({xh, yv});
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (vis[x][y]) continue;
        vis[x][y] = 1;
        
        // mutam verticala la dreapta
        if (y + 1 <= w && inter(up[x][y], down[x][y], up[x][y + 1], down[x][y + 1]) >= l) {
            q.push({x, y + 1});
        }
        // mutam verticala la stanga
        if (y - 1 >= 1 && inter(up[x][y], down[x][y], up[x][y - 1], down[x][y - 1]) >= l) {
            q.push({x, y - 1});
        }
        // mutam orizontala in jos
        if (x + 1 <= h && inter(lft[x][y], rgh[x][y], lft[x + 1][y], rgh[x + 1][y]) >= k) {
            q.push({x + 1, y});
        }
        // mutam orizontala in sus
        if (x - 1 >= 1 && inter(lft[x][y], rgh[x][y], lft[x - 1][y], rgh[x - 1][y]) >= k) {
            q.push({x - 1, y});
        }
    }
    cout << (vis[xf][yf] ? "YES" : "NO") << "\n";
    return 0;
}

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