Submission #1070554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070554		faruk	Toy (CEOI24_toy)	C++17	100 / 100	119 ms	56448 KiB

Main

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<string> grid;
vector<vector<int> > max_up, max_right, can_hori, can_vert, box_hori, box_vert;
int n, m;

bool check_box_hori(int i, int j1, int j2) {
    j1 = max(j1, 0);
    j2 = min(j2, m - 1);
    if (j1 > j2)
        return 0;
    int v1 = box_hori[i][j1];
    if (j2 != m - 1)
        v1 -= box_hori[i][j2 + 1];
    return v1 > 0;
}

bool check_box_vert(int i1, int i2, int j) {
    i1 = max(i1, 0);
    i2 = min(i2, n - 1);
    if (i1 > i2)
        return 0;
    int v2 = box_vert[i2][j];
    if (i1 != 0)
        v2 -= box_vert[i1 - 1][j];
    return v2;
}

int get_num_ok_hori(int i, int j1, int j2) {
    j1 = max(j1, 0);
    j2 = min(j2, m - 1);
    if (j1 > j2)
        return 0;
    int v1 = can_hori[i][j1];
    if (j2 != m - 1)
        v1 -= can_hori[i][j2 + 1];
    return v1;
}

int get_num_ok_vert(int i1, int i2, int j) {
    i1 = max(i1, 0);
    i2 = min(i2, n - 1);
    if (i1 > i2)
        return 0;
    int v2 = can_vert[i2][j];
    if (i1 != 0)
        v2 -= can_vert[i1 - 1][j];
    return v2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int w, h;
    cin >> m >> n >> w >> h;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    pii strt(y1, x2);

    pii endd;
    grid = vector<string>(n);
    for (int i = 0; i < n; i++)
        cin >> grid[i];
    max_up = max_right = can_hori = can_vert = box_hori = box_vert = vector<vector<int> > (n + 1, vector<int>(m + 1));
    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            if (grid[i][j] == '*')
                endd = pii(i, j);
            if (grid[i][j] == '.' || grid[i][j] == '*')
                max_up[i][j] = max_right[i][j] = 1;
            if (i != 0 and max_up[i][j] != 0)
                max_up[i][j] += max_up[i - 1][j];
            if (j != m - 1 and max_up[i][j] != 0)
                max_right[i][j] += max_right[i][j + 1];
            
            if (max_up[i][j] >= h)
                can_vert[i][j] = 1;
            if (max_right[i][j] >= w)
                can_hori[i][j] = 1;

            if (j != m - 1)
                if (can_vert[i][j] and can_vert[i][j + 1])
                    box_vert[i][j] = 1;
            if (i != 0)
                if (can_hori[i - 1][j] and can_hori[i][j])
                    box_hori[i][j] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            if (j != m - 1)
                box_hori[i][j] += box_hori[i][j + 1], can_hori[i][j] += can_hori[i][j + 1];
            if (i != 0)
                box_vert[i][j] += box_vert[i - 1][j], can_vert[i][j] += can_vert[i - 1][j];
        }
    }

    vector<vector<bool> > vis(n, vector<bool> (m));
    vis[strt.first][strt.second] = true;

    queue<pii> qu;
    qu.push(strt);
    while (!qu.empty()) {
        pii curr = qu.front(); qu.pop();

        // try moving vert to front
        int i1 = curr.first, i2 = curr.first + h - 1;
        if (curr.second != m - 1 and !vis[curr.first][curr.second + 1] and check_box_vert(i1, i2, curr.second))
        {
            // add anoterh
            if (get_num_ok_hori(curr.first, curr.second - (w - 2), curr.second) > 0) {
                vis[curr.first][curr.second + 1] = true;
                qu.push(pii(curr.first, curr.second + 1));
            }
        }
        // try moving back
        if (curr.second != 0 and !vis[curr.first][curr.second - 1] and check_box_vert(i1, i2, curr.second - 1))
        {
            // add anotehr
            if (get_num_ok_hori(curr.first, curr.second - (w - 1), curr.second - 1) > 0) {
                vis[curr.first][curr.second - 1] = true;
                qu.push(pii(curr.first, curr.second - 1));
            }
        }

        // try moving hori up
        int j1 = curr.second - w + 1, j2 = curr.second;
        if (curr.first != 0 and !vis[curr.first - 1][curr.second] and check_box_hori(curr.first, j1, j2)) {
            if (get_num_ok_vert(curr.first, curr.first + (h - 2), curr.second) > 0) {
                vis[curr.first - 1][curr.second] = true;
                qu.push(pii(curr.first - 1, curr.second));
            }
        }

        // try moving hori down
        if (curr.first != n - 1 and !vis[curr.first + 1][curr.second] and check_box_hori(curr.first + 1, j1, j2)) {
            if (get_num_ok_vert(curr.first + 1, curr.first + (h - 1), curr.second) > 0) {
                vis[curr.first + 1][curr.second] = true;
                qu.push(pii(curr.first + 1, curr.second));
            }
        }
    }

    
    if (vis[endd.first][endd.second])   
        cout << "YES\n";
    else
        cout << "NO\n";
}

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