제출 #1123401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123401		serifefedartar	Toy (CEOI24_toy)	C++20	0 / 100	28 ms	20804 KiB

Main

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

#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 1600;

int W, H, hor, ver, ver_check[MAXN][MAXN], hor_check[MAXN][MAXN];
int ver_col, ver_row, hor_col, hor_row, hor_all[MAXN][MAXN], ver_all[MAXN][MAXN];
int pref[MAXN][MAXN], pref2[MAXN][MAXN], vis[MAXN][MAXN];
string grid[MAXN];

bool check(int r1, int c1, int r2, int c2) {
    if (r1 > H || r2 > H || c1 > W || c2 > W || r1 < 1 || r2 < 1 || c1 < 1 || c2 < 1)
        return false;
    if (r1 == r2 && pref[r1][c1-1] == pref[r1][c2])
        return true;
    if (c1 == c2 && pref2[r2][c1] == pref2[r1-1][c1])
        return true;
    return false;
}

void vertical(int R, int C) {
    int dr[] = {-1, 0, 1, 0};
    int dc[] = {0, 1, 0, -1};
    for (int i = 0; i < 4; i++) {
        int nr = R + dr[i];
        int nc = C + dc[i];
        if (nr > H || nr < 1 || nc > W || nc < 1)
            continue;
        if (check(nr, nc, nr + ver - 1, nc) && !ver_check[nr][nc]) {
            ver_check[nr][nc] = true;
            vertical(nr, nc);
        }
    }
}

void horizontal(int R, int C) {
    int dr[] = {-1, 0, 1, 0};
    int dc[] = {0, 1, 0, -1};
    for (int i = 0; i < 4; i++) {
        int nr = R + dr[i];
        int nc = C + dc[i];
        if (nr > H || nr < 1 || nc > W || nc < 1)
            continue;
        if (check(nr, nc, nr, nc + hor - 1) && !hor_check[nr][nc]) {
            hor_check[nr][nc] = true;
            horizontal(nr, nc);
        }
    }
}

bool result(int row, int col) {
    if (grid[row][col] == '*')
        return true;
    if (vis[row][col])
        return false;
    vis[row][col] = true;

    int dr[] = {-1, 0, 1, 0};
    int dc[] = {0, 1, 0, -1};
    bool ans = false;
    for (int i = 0; i < 4; i++) {
        int nr = row + dr[i];
        int nc = col + dc[i];
        if (nr > H || nr < 1 || nc > W || nc < 1)
            continue;
        if (hor_all[nr][nc] && ver_all[nr][nc])
            ans |= result(nr, nc);
    }
    return ans;
}

int main() {
    fast;
    cin >> W >> H >> hor >> ver;
    cin >> ver_col >> ver_row >> hor_col >> hor_row;
    ver_col++; ver_row++; hor_col++; hor_row++;

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

    vertical(ver_row, ver_col);
    horizontal(hor_row, hor_col);

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (hor_check[i][j]) {
                hor_all[i][j]++;
                if (j + hor - 1 <= 1550)
                    hor_all[i][j + hor]--;
            }
        }
    }

    for (int j = 1; j <= W; j++) {
        for (int i = 1; i <= H; i++) {
            if (ver_check[i][j]) {
                ver_all[i][j]++;
                if (i + ver - 1 <= 1550)
                    ver_all[i + ver][j]--;
            }
        }
    }

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++)
            hor_all[i][j] += hor_all[i][j-1];
    }
    for (int j = 1; j <= W; j++) {
        for (int i = 1; i <= H; i++) 
            ver_all[i][j] += ver_all[i-1][j];
    }

    if (result(hor_row, ver_col))
        cout << "YES\n";
    else
        cout << "NO\n";
}

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