oj.uz

Submission #241300

# Submission time Handle Problem Language Result Execution time Memory
241300 2020-06-23T18:07:07 Z dolphingarlic Robots (APIO13_robots) C++14
60 / 100
 1500 ms 89608 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const int INF = 1061109567;

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

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;
            priority_queue<pair<int, pair<int, int>>> pq;
            FOR(i, 0, h) FOR(j, 0, w) {
                if (dp[i][j][k][l] != INF && g[i][j] != 'x') {
                    pq.push({-dp[i][j][k][l], {i, j}});
                }
            }
            while (pq.size()) {
                int x, y;
                tie(x, y) = pq.top().second;
                pq.pop();
                FOR(dir, 0, 4) {
                    int nx, ny;
                    tie(nx, ny) = end_pos[x][y][dir];
                    if (dp[nx][ny][k][l] > dp[x][y][k][l] + 1) {
                        dp[nx][ny][k][l] = dp[x][y][k][l] + 1;
                        pq.push({-dp[nx][ny][k][l], {nx, ny}});
                    }
                }
            }
        }
    }

    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 45 ms 79608 KB Output is correct
2 Correct 50 ms 79612 KB Output is correct
3 Correct 45 ms 79608 KB Output is correct
4 Correct 47 ms 79608 KB Output is correct
5 Correct 46 ms 79608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 79608 KB Output is correct
2 Correct 50 ms 79612 KB Output is correct
3 Correct 45 ms 79608 KB Output is correct
4 Correct 47 ms 79608 KB Output is correct
5 Correct 46 ms 79608 KB Output is correct
6 Correct 46 ms 79608 KB Output is correct
7 Correct 47 ms 79608 KB Output is correct
8 Correct 48 ms 79612 KB Output is correct
9 Correct 49 ms 79608 KB Output is correct
10 Correct 46 ms 79612 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 79608 KB Output is correct
2 Correct 50 ms 79612 KB Output is correct
3 Correct 45 ms 79608 KB Output is correct
4 Correct 47 ms 79608 KB Output is correct
5 Correct 46 ms 79608 KB Output is correct
6 Correct 46 ms 79608 KB Output is correct
7 Correct 47 ms 79608 KB Output is correct
8 Correct 48 ms 79612 KB Output is correct
9 Correct 49 ms 79608 KB Output is correct
10 Correct 46 ms 79612 KB Output is correct
11 Correct 274 ms 83756 KB Output is correct
12 Correct 55 ms 83064 KB Output is correct
13 Correct 137 ms 83836 KB Output is correct
14 Correct 823 ms 84496 KB Output is correct
15 Correct 187 ms 83432 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 79608 KB Output is correct
2 Correct 50 ms 79612 KB Output is correct
3 Correct 45 ms 79608 KB Output is correct
4 Correct 47 ms 79608 KB Output is correct
5 Correct 46 ms 79608 KB Output is correct
6 Correct 46 ms 79608 KB Output is correct
7 Correct 47 ms 79608 KB Output is correct
8 Correct 48 ms 79612 KB Output is correct
9 Correct 49 ms 79608 KB Output is correct
10 Correct 46 ms 79612 KB Output is correct
11 Correct 274 ms 83756 KB Output is correct
12 Correct 55 ms 83064 KB Output is correct
13 Correct 137 ms 83836 KB Output is correct
14 Correct 823 ms 84496 KB Output is correct
15 Correct 187 ms 83432 KB Output is correct
16 Correct 623 ms 88056 KB Output is correct
17 Execution timed out 1592 ms 89608 KB Time limit exceeded
18 Halted 0 ms 0 KB -