Submission #623240

#	Time	Username	Problem	Language	Result	Execution time	Memory
623240		jhwest2	Robots (APIO13_robots)	C++17	60 / 100	1556 ms	49392 KiB

robots

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

const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { -1, 0, 1, 0 };
const int INF = 0x3f3f3f3f;

int n, w, h, go[1515151], a[1515151];
int dist[505][505], dp[9][9][505][505], g[505][505];
string S[505];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++) {
        cin >> S[i];
    }
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        int x = w * i + j;
        int y[4] = {};
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (ni < 0 || nj < 0 || ni >= h || nj >= w || S[ni][nj] == 'x') {
                y[k] = -1;
            }
            else y[k] = w * ni + nj;
        }
        go[5 * x] = 5 * x;
        for (int k = 0; k < 4; k++) {
            if (S[i][j] == 'A') {
                if (y[(k + 1) % 4] == -1) {
                    go[5 * x + 1 + k] = 5 * x;
                }
                else go[5 * x + 1 + k] = 5 * y[(k + 1) % 4] + 1 + (k + 1) % 4;
            }
            else if (S[i][j] == 'C') {
                if (y[(k + 3) % 4] == -1) {
                    go[5 * x + 1 + k] = 5 * x;
                }
                else go[5 * x + 1 + k] = 5 * y[(k + 3) % 4] + 1 + (k + 3) % 4;
            }
            else if (S[i][j] != 'x') {
                if (y[k] == -1) {
                    go[5 * x + 1 + k] = 5 * x;
                }
                else go[5 * x + 1 + k] = 5 * y[k] + 1 + k;
            }
        }
    }
    for (int k = 0; k < 30; k++) {
        for (int i = 0; i < 5 * w * h; i++) {
            go[i] = go[go[i]];
        }
    }
    
    iota(a, a + w * h, 0);
    for (int d = 0; d < n; d++) for (int i = 0; i < n - d; i++) {
        int j = i + d;
        for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
            g[x][y] = INF;
            if (d == 0) {
                g[x][y] = (S[x][y] - '1' == i) ? 0 : INF;
            }
            else {
                for (int k = i; k < j; k++) {
                    g[x][y] = min(g[x][y], dp[i][k][x][y] + dp[k + 1][j][x][y]);
                }
            }
        }
        memset(dist, 0x3f, sizeof dist);
        sort(a, a + w * h, [&](int i, int j) {
            return g[i / w][i % w] < g[j / w][j % w];
            });

        queue<pair<int, int>> Q, R;
        for (int i = 0; i < w * h; i++) {
            if (g[a[i] / w][a[i] % w] != INF) {
                Q.emplace(5 * a[i], g[a[i] / w][a[i] % w]);
            }
            else break;
        }
        while (!Q.empty() || !R.empty()) {
            int v, d;
            if (Q.empty() || (!R.empty() && Q.front().second >= R.front().second)) {
                tie(v, d) = R.front(); R.pop();
            }
            else {
                tie(v, d) = Q.front(); Q.pop();
            }
            // cout << i << ' ' << j << ' ' << "(" << (v / 5 / w) << ", " << (v / 5 % w) << ") " << ' ' << d << '\n';
            assert(v % 5 == 0);
            
            if (dist[v / 5 / w][v / 5 % w] != INF) continue;
            dist[v / 5 / w][v / 5 % w] = d;
            
            for (int k = 1; k <= 4; k++) {
                if (go[v + k] % 5 != 0) continue;
                R.emplace(go[v + k], d + 1);
            }
        }
        for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
            dp[i][j][x][y] = dist[x][y];
        }
    }
    int ans = INF;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        ans = min(ans, dp[0][n - 1][i][j]);
    }
    cout << (ans == INF ? -1 : ans);
}

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