oj.uz

Submission #733177

# Submission time Handle Problem Language Result Execution time Memory
733177 2023-04-30T07:55:32 Z CyberCraze Robots (APIO13_robots) C++17
100 / 100
 858 ms 124704 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 35 ms 85324 KB Output is correct
2 Correct 34 ms 85448 KB Output is correct
3 Correct 40 ms 85324 KB Output is correct
4 Correct 37 ms 85564 KB Output is correct
5 Correct 37 ms 85416 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 85324 KB Output is correct
2 Correct 34 ms 85448 KB Output is correct
3 Correct 40 ms 85324 KB Output is correct
4 Correct 37 ms 85564 KB Output is correct
5 Correct 37 ms 85416 KB Output is correct
6 Correct 34 ms 85336 KB Output is correct
7 Correct 34 ms 85324 KB Output is correct
8 Correct 36 ms 85416 KB Output is correct
9 Correct 35 ms 85424 KB Output is correct
10 Correct 35 ms 85460 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 85324 KB Output is correct
2 Correct 34 ms 85448 KB Output is correct
3 Correct 40 ms 85324 KB Output is correct
4 Correct 37 ms 85564 KB Output is correct
5 Correct 37 ms 85416 KB Output is correct
6 Correct 34 ms 85336 KB Output is correct
7 Correct 34 ms 85324 KB Output is correct
8 Correct 36 ms 85416 KB Output is correct
9 Correct 35 ms 85424 KB Output is correct
10 Correct 35 ms 85460 KB Output is correct
11 Correct 167 ms 92896 KB Output is correct
12 Correct 40 ms 89396 KB Output is correct
13 Correct 121 ms 89664 KB Output is correct
14 Correct 257 ms 97896 KB Output is correct
15 Correct 127 ms 90060 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 85324 KB Output is correct
2 Correct 34 ms 85448 KB Output is correct
3 Correct 40 ms 85324 KB Output is correct
4 Correct 37 ms 85564 KB Output is correct
5 Correct 37 ms 85416 KB Output is correct
6 Correct 34 ms 85336 KB Output is correct
7 Correct 34 ms 85324 KB Output is correct
8 Correct 36 ms 85416 KB Output is correct
9 Correct 35 ms 85424 KB Output is correct
10 Correct 35 ms 85460 KB Output is correct
11 Correct 167 ms 92896 KB Output is correct
12 Correct 40 ms 89396 KB Output is correct
13 Correct 121 ms 89664 KB Output is correct
14 Correct 257 ms 97896 KB Output is correct
15 Correct 127 ms 90060 KB Output is correct
16 Correct 598 ms 93756 KB Output is correct
17 Correct 858 ms 124704 KB Output is correct
18 Correct 318 ms 96404 KB Output is correct
19 Correct 373 ms 93820 KB Output is correct
20 Correct 551 ms 107284 KB Output is correct