Submission #384741

#	Time	Username	Problem	Language	Result	Execution time	Memory
384741		ParsaAlizadeh	Robots (APIO13_robots)	C++17	100 / 100	600 ms	85512 KiB

robots

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

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

#define all(x)          begin(x), end(x)
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'

constexpr int W   = 500;
constexpr int N   = 9;
constexpr int INF = W * W + 1;

int n, w, h, nxt[W * W][4], dp[N][N][W * W];
int dj[] = {+1, 0, -1, 0}, di[] = {0, -1, 0, +1};
char board[W][W];

int memoiz(int i, int j, int dir) {
    int ij = i * h + j;
    if (nxt[ij][dir] >= -1)
        return nxt[ij][dir];
    nxt[ij][dir] = -1;
    int dir_ = dir;
    if (board[i][j] == 'A')
        dir_ = (dir + 1) % 4;
    if (board[i][j] == 'C')
        dir_ = (dir + 3) % 4;
    int i_ = i + di[dir_], j_ = j + dj[dir_];
    if (i_ < 0 || i_ >= w || j_ < 0 || j_ >= h || board[i_][j_] == 'x')
        return nxt[ij][dir] = ij;
    return nxt[ij][dir] = memoiz(i_, j_, dir_);
}

inline int popitem(queue<int> & q) {
    int res = q.front(); q.pop();
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> h >> w;
    for (int i = 0; i < w; i++)
    for (int j = 0; j < h; j++)
        cin >> board[i][j];

    memset(nxt, 0x80, sizeof(nxt));
    for (int i = 0; i < w; i++)
    for (int j = 0; j < h; j++) {
        int ij = i * h + j;
        for (int dir : {0, 1, 2, 3})
            nxt[ij][dir] = board[i][j] == 'x' ? -1 : memoiz(i, j, dir);
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int r = 0; r < n; r++)
    for (int l = r; l >= 0; l--) {
        auto dp_ = dp[l][r];
        vector<int> vec;
        if (l == r) {
            for (int i = 0; i < w; i++)
            for (int j = 0; j < h; j++) {
                int ij = i * h + j;
                if (board[i][j] == l + '1')
                    dp_[ij] = 0, vec.push_back(ij);
            }
        }
        else {
            for (int i = 0; i < w; i++)
            for (int j = 0; j < h; j++) {
                int ij = i * h + j;
                for (int k = l; k < r; k++)
                    dp_[ij] = min(dp_[ij], dp[l][k][ij] + dp[k + 1][r][ij]);
                if (dp_[ij] < INF)
                    vec.push_back(ij);
            }
        }
        sort(all(vec), [&dp_] (int u, int v) {
            return dp_[u] < dp_[v];
        });
        queue<int> q1, q2;
        for (int u : vec)
            q1.push(u);
        while (!q1.empty() || !q2.empty()) {
            int ij = (q1.empty() || (!q2.empty() && dp_[q2.front()] < dp_[q1.front()]) ? popitem(q2) : popitem(q1));
            for (int dir : {0, 1, 2, 3}) {
                int v = nxt[ij][dir];
                if (v != -1 && dp_[v] > dp_[ij] + 1) {
                    dp_[v] = dp_[ij] + 1;
                    q2.push(v);
                }
            }
        }
    }

    int ans = *min_element(all(dp[0][n - 1]));
    cout << (ans < INF ? ans : -1) << endl;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40