Submission #1214793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214793		spetr	Toy (CEOI24_toy)	C++20	100 / 100	175 ms	222824 KiB

Main

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

const int MAXN = 1505;
int w, h, k, l;
int mat[MAXN][MAXN];       // 0=empty, 1=obstacle, 2=target
bool vis[MAXN][MAXN];
int dp[MAXN][MAXN][4];     // 0:left,1:up,2:right,3:down

inline int intersect(int l1, int r1, int l2, int r2) {
    return max(0, min(r1, r2) - max(l1, l2) + 1);
}

void dfs(int y, int x) {
    vis[y][x] = true;
    if (mat[y][x] == 2) {
        cout << "YES";
        exit(0);
    }
    static const int dy[4] = {0, 0, 1, -1};
    static const int dx[4] = {1, -1, 0, 0};
    
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
        if (mat[ny][nx] == 1 || vis[ny][nx]) continue;
        int l1 = x - dp[y][x][0] + 1;
        int r1 = x + dp[y][x][2] - 1;
        int l2 = nx - dp[ny][nx][0] + 1;
        int r2 = nx + dp[ny][nx][2] - 1;
        if (intersect(l1, r1, l2, r2) < k) continue;
        int u1 = y - dp[y][x][1] + 1;
        int d1 = y + dp[y][x][3] - 1;
        int u2 = ny - dp[ny][nx][1] + 1;
        int d2 = ny + dp[ny][nx][3] - 1;
        if (intersect(u1, d1, u2, d2) < l) continue;
        dfs(ny, nx);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int sx, sy, dummy;
    cin >> w >> h >> k >> l;
    cin >> dummy >> sy >> sx >> dummy;

    // read grid and init mat
    for (int i = 0; i < h; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < w; j++) {
            if (row[j] == 'X') mat[i][j] = 1;
            else if (row[j] == '*') mat[i][j] = 2;
            else mat[i][j] = 0;
        }
    }

    // precompute dp
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (mat[i][j] == 1) continue;
            dp[i][j][0] = (j>0 && mat[i][j-1]!=1 ? dp[i][j-1][0] + 1 : 1);
            dp[i][j][1] = (i>0 && mat[i-1][j]!=1 ? dp[i-1][j][1] + 1 : 1);
        }
    }
    for (int i = h-1; i >= 0; i--) {
        for (int j = w-1; j >= 0; j--) {
            if (mat[i][j] == 1) continue;
            dp[i][j][2] = (j+1<w && mat[i][j+1]!=1 ? dp[i][j+1][2] + 1 : 1);
            dp[i][j][3] = (i+1<h && mat[i+1][j]!=1 ? dp[i+1][j][3] + 1 : 1);
        }
    }

    dfs(sy, sx);
    cout << "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