oj.uz

Submission #241285

# Submission time Handle Problem Language Result Execution time Memory
241285 2020-06-23T16:31:20 Z dolphingarlic Robots (APIO13_robots) C++14
60 / 100
 1500 ms 91144 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 grid[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 && grid[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 >> grid[i][j];
        if (grid[i][j] - '0' > 0 && grid[i][j] - '0' < 10) {
            dp[i][j][grid[i][j] - '1'][grid[i][j] - '1'] = 0;
        }
    }

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

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

            if (grid[curr_pos.first][curr_pos.second] == 'A') {
                curr_dir = (curr_dir + 3) % 4;
            } else if (grid[curr_pos.first][curr_pos.second] == 'C') {
                curr_dir = (curr_dir + 1) % 4;
            }
        }

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

    FOR(rng, 0, n) {
        FOR(k, 0, n - rng) {
            int l = k + rng;
            FOR(div, k, l) FOR(i, 0, h) FOR(j, 0, w) {
                dp[i][j][k][l] = min(dp[i][j][k][l],
                                     dp[i][j][k][div] + dp[i][j][div + 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 && grid[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 53 ms 79612 KB Output is correct
2 Correct 52 ms 79608 KB Output is correct
3 Correct 46 ms 79612 KB Output is correct
4 Correct 46 ms 79744 KB Output is correct
5 Correct 46 ms 79572 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 79612 KB Output is correct
2 Correct 52 ms 79608 KB Output is correct
3 Correct 46 ms 79612 KB Output is correct
4 Correct 46 ms 79744 KB Output is correct
5 Correct 46 ms 79572 KB Output is correct
6 Correct 50 ms 79608 KB Output is correct
7 Correct 46 ms 79608 KB Output is correct
8 Correct 46 ms 79608 KB Output is correct
9 Correct 46 ms 79608 KB Output is correct
10 Correct 46 ms 79608 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 79612 KB Output is correct
2 Correct 52 ms 79608 KB Output is correct
3 Correct 46 ms 79612 KB Output is correct
4 Correct 46 ms 79744 KB Output is correct
5 Correct 46 ms 79572 KB Output is correct
6 Correct 50 ms 79608 KB Output is correct
7 Correct 46 ms 79608 KB Output is correct
8 Correct 46 ms 79608 KB Output is correct
9 Correct 46 ms 79608 KB Output is correct
10 Correct 46 ms 79608 KB Output is correct
11 Correct 370 ms 84516 KB Output is correct
12 Correct 55 ms 83832 KB Output is correct
13 Correct 177 ms 83832 KB Output is correct
14 Correct 941 ms 85296 KB Output is correct
15 Correct 334 ms 84196 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 79612 KB Output is correct
2 Correct 52 ms 79608 KB Output is correct
3 Correct 46 ms 79612 KB Output is correct
4 Correct 46 ms 79744 KB Output is correct
5 Correct 46 ms 79572 KB Output is correct
6 Correct 50 ms 79608 KB Output is correct
7 Correct 46 ms 79608 KB Output is correct
8 Correct 46 ms 79608 KB Output is correct
9 Correct 46 ms 79608 KB Output is correct
10 Correct 46 ms 79608 KB Output is correct
11 Correct 370 ms 84516 KB Output is correct
12 Correct 55 ms 83832 KB Output is correct
13 Correct 177 ms 83832 KB Output is correct
14 Correct 941 ms 85296 KB Output is correct
15 Correct 334 ms 84196 KB Output is correct
16 Correct 916 ms 87928 KB Output is correct
17 Execution timed out 1600 ms 91144 KB Time limit exceeded
18 Halted 0 ms 0 KB -