oj.uz

Submission #738021

# Submission time Handle Problem Language Result Execution time Memory
738021 2023-05-08T05:36:34 Z vjudge1 Robots (APIO13_robots) C++17
100 / 100
 749 ms 124504 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

const int INF = 250000;

int n, h, w;
char g[500][500];
pair<int, int> end_pos[500][500][4];
int dp[500][500][9][9];
vector<pair<int, int>> q[INF];

bool inside(int x, int y) {
    return (x >= 0 && y >= 0 && x < h && y < w && g[x][y] != 'x');
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> w >> h;
    memset(dp, 0x3f, sizeof(dp));

    FOR(i, 0, h) FOR(j, 0, w) {
        cin >> g[i][j];
        if (g[i][j] - '0' > 0 && g[i][j] - '0' < 10) {
            dp[i][j][g[i][j] - '1'][g[i][j] - '1'] = 0;
        }
    }

    // Determine final positions from each push
    FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
        FOR(k, 0, 4) {
            pair<int, int> pos = {i, j};
            int d = (k + (g[i][j] == 'A') * 3 + (g[i][j] == 'C')) % 4;  // NESW

            while (true) {
                if (d == 0) {
                    if (inside(pos.first - 1, pos.second)) pos.first--;
                    else break;
                } else if (d == 1) {
                    if (inside(pos.first, pos.second + 1)) pos.second++;
                    else break;
                } else if (d == 2) {
                    if (inside(pos.first + 1, pos.second)) pos.first++;
                    else break;
                } else {
                    if (inside(pos.first, pos.second - 1)) pos.second--;
                    else break;
                }

                if (g[pos.first][pos.second] == 'A') d = (d + 3) % 4;
                if (g[pos.first][pos.second] == 'C') d = (d + 1) % 4;
            }

            end_pos[i][j][k] = pos;
        }
    }

    // Find the minimum no. of pushes to get robot k-l to block (i, j)
    FOR(rng, 0, n) {
        FOR(k, 0, n - rng) {
            int l = k + rng;
            FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
                FOR(d, k, l) {
                    dp[i][j][k][l] =
                        min(dp[i][j][k][l],
                            dp[i][j][k][d] + dp[i][j][d + 1][l]);
                }
            }
        }

        FOR(k, 0, n - rng) {
            int l = k + rng;

            FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
                if (dp[i][j][k][l] <= INF) q[dp[i][j][k][l]].push_back({i, j});
            }
            
            FOR(i, 0, INF) {
                for (pair<int, int> pos : q[i]) {
                    int x, y;
                    tie(x, y) = pos;
                    if (dp[x][y][k][l] == i) {
                        FOR(d, 0, 4) {
                            int nx, ny;
                            tie(nx, ny) = end_pos[x][y][d];
                            if (dp[nx][ny][k][l] > dp[x][y][k][l] + 1) {
                                q[dp[nx][ny][k][l] = dp[x][y][k][l] + 1].push_back({nx, ny});
                            }
                        }
                    }
                }
                q[i].clear();
            }
        }
    }

    int ans = INT_MAX;
    FOR(i, 0, h) FOR(j, 0, w) ans = min(ans, dp[i][j][0][n - 1]);
    cout << (ans > INF ? -1 : ans);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 85328 KB Output is correct
2 Correct 34 ms 85520 KB Output is correct
3 Correct 35 ms 85404 KB Output is correct
4 Correct 33 ms 85476 KB Output is correct
5 Correct 33 ms 85452 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 85328 KB Output is correct
2 Correct 34 ms 85520 KB Output is correct
3 Correct 35 ms 85404 KB Output is correct
4 Correct 33 ms 85476 KB Output is correct
5 Correct 33 ms 85452 KB Output is correct
6 Correct 33 ms 85452 KB Output is correct
7 Correct 34 ms 85436 KB Output is correct
8 Correct 34 ms 85364 KB Output is correct
9 Correct 34 ms 85324 KB Output is correct
10 Correct 33 ms 85440 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 85328 KB Output is correct
2 Correct 34 ms 85520 KB Output is correct
3 Correct 35 ms 85404 KB Output is correct
4 Correct 33 ms 85476 KB Output is correct
5 Correct 33 ms 85452 KB Output is correct
6 Correct 33 ms 85452 KB Output is correct
7 Correct 34 ms 85436 KB Output is correct
8 Correct 34 ms 85364 KB Output is correct
9 Correct 34 ms 85324 KB Output is correct
10 Correct 33 ms 85440 KB Output is correct
11 Correct 146 ms 92748 KB Output is correct
12 Correct 39 ms 89328 KB Output is correct
13 Correct 117 ms 89668 KB Output is correct
14 Correct 285 ms 97844 KB Output is correct
15 Correct 128 ms 90008 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 85328 KB Output is correct
2 Correct 34 ms 85520 KB Output is correct
3 Correct 35 ms 85404 KB Output is correct
4 Correct 33 ms 85476 KB Output is correct
5 Correct 33 ms 85452 KB Output is correct
6 Correct 33 ms 85452 KB Output is correct
7 Correct 34 ms 85436 KB Output is correct
8 Correct 34 ms 85364 KB Output is correct
9 Correct 34 ms 85324 KB Output is correct
10 Correct 33 ms 85440 KB Output is correct
11 Correct 146 ms 92748 KB Output is correct
12 Correct 39 ms 89328 KB Output is correct
13 Correct 117 ms 89668 KB Output is correct
14 Correct 285 ms 97844 KB Output is correct
15 Correct 128 ms 90008 KB Output is correct
16 Correct 537 ms 93756 KB Output is correct
17 Correct 749 ms 124504 KB Output is correct
18 Correct 285 ms 96296 KB Output is correct
19 Correct 389 ms 93728 KB Output is correct
20 Correct 523 ms 107148 KB Output is correct