Submission #1075715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075715		raphaelp	Toy (CEOI24_toy)	C++14	100 / 100	208 ms	46864 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int W, H, K, L;
    cin >> W >> H >> L >> K;
    vector<vector<int>> dp(H, vector<int>(W, 0));
    vector<vector<pair<int, int>>> cumH(H, vector<pair<int, int>>(W, {1000000, 1000000})), cumW(H, vector<pair<int, int>>(W, {1000000, 1000000}));
    int x1, x2, y1, y2;
    queue<pair<int, int>> Q;
    cin >> y1 >> x1 >> y2 >> x2;
    Q.push({x1, y2});
    pair<int, int> targ;
    for (int i = 0; i < H; i++)
    {
        string S;
        cin >> S;
        for (int j = 0; j < W; j++)
        {
            if (S[j] == '*')
                targ = {i, j};
            if (S[j] == 'X')
            {
                cumH[i][j].first = 0;
                cumH[i][j].second = 0;
                cumW[i][j].first = 0;
                cumW[i][j].second = 0;
            }
        }
    }
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (i == 0)
            {
                cumH[i][j].first = min(cumH[i][j].first, 1);
            }
            else
            {
                cumH[i][j].first = min(cumH[i][j].first, cumH[i - 1][j].first + 1);
            }
            if (j == 0)
            {
                cumW[i][j].first = min(cumW[i][j].first, 1);
            }
            else
            {
                cumW[i][j].first = min(cumW[i][j].first, cumW[i][j - 1].first + 1);
            }
        }
    }
    for (int i = H - 1; i >= 0; i--)
    {
        for (int j = W - 1; j >= 0; j--)
        {
            if (i == H - 1)
            {
                cumH[i][j].second = min(cumH[i][j].second, 1);
            }
            else
            {
                cumH[i][j].second = min(cumH[i][j].second, cumH[i + 1][j].second + 1);
            }
            if (j == W - 1)
            {
                cumW[i][j].second = min(cumW[i][j].second, 1);
            }
            else
            {
                cumW[i][j].second = min(cumW[i][j].second, cumW[i][j + 1].second + 1);
            }
        }
    }
    while (!Q.empty())
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        if (dp[x][y])
            continue;
        dp[x][y] = 1;
        if (x > 0)
        {
            if (min(cumW[x][y].first, cumW[x - 1][y].first) + min(cumW[x][y].second, cumW[x - 1][y].second) > L)
            {
                Q.push({x - 1, y});
            }
        }
        if (x < H - 1)
        {
            if (min(cumW[x][y].first, cumW[x + 1][y].first) + min(cumW[x][y].second, cumW[x + 1][y].second) > L)
            {
                Q.push({x + 1, y});
            }
        }
        if (y > 0)
        {
            if (min(cumH[x][y].first, cumH[x][y - 1].first) + min(cumH[x][y].second, cumH[x][y - 1].second) > K)
            {
                Q.push({x, y - 1});
            }
        }
        if (y < W - 1)
        {
            if (min(cumH[x][y].first, cumH[x][y + 1].first) + min(cumH[x][y].second, cumH[x][y + 1].second) > K)
            {
                Q.push({x, y + 1});
            }
        }
    }
    if (dp[targ.first][targ.second])
        cout << "YES";
    else
        cout << "NO";
}

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