oj.uz

Submission #563408

# Submission time Handle Problem Language Result Execution time Memory
563408 2022-05-17T06:44:43 Z KoD Robots (APIO13_robots) C++17
100 / 100
 1375 ms 100340 KB 
#include <bits/stdc++.h>

using std::pair;
using std::tuple;
using std::vector;
using std::array;

constexpr int MAX = 500;
constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr int DI[] = {0, 1, 0, -1};
constexpr int DJ[] = {1, 0, -1, 0};

char grid[MAX + 2][MAX + 2];
int dist[MAX + 2][MAX + 2][9][9];
int state[MAX + 2][MAX + 2][4];
pair<int, int> stops[MAX + 2][MAX + 2][4];

pair<int, int> dfs(const int i, const int j, const int k) {
    if (state[i][j][k] == 2) {
        return stops[i][j][k];
    }
    if (state[i][j][k] == 1) {
        return stops[i][j][k] = {i, j};
    }
    state[i][j][k] = 1;
    int nk = k;
    if (grid[i][j] == 'A') {
        nk = (k + 3) % 4;
    }
    if (grid[i][j] == 'C') {
        nk = (k + 1) % 4;
    }
    const int ni = i + DI[nk], nj = j + DJ[nk];
    if (grid[ni][nj] == 'x') {
        state[i][j][k] = 2;
        return stops[i][j][k] = {i, j};
    } else {
        stops[i][j][k] = dfs(ni, nj, nk);
        if (state[ni][nj][nk] == 1) {
            stops[i][j][k] = {i, j};
        } else {
            state[i][j][k] = 2;
        }
        return stops[i][j][k];
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, H, W;
    std::cin >> N >> W >> H;
    H += 2, W += 2;
    for (int i = 0; i < W; ++i) {
        grid[0][i] = grid[H - 1][i] = 'x';
    }
    for (int i = 0; i < H; ++i) {
        grid[i][0] = grid[i][W - 1] = 'x';
    }
    for (int i = 1; i < H - 1; ++i) {
        for (int j = 1; j < W - 1; ++j) {
            std::cin >> grid[i][j];
        }
    }
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            for (int k = 0; k < N; ++k) {
                for (int l = 0; l < N; ++l) {
                    dist[i][j][k][l] = INF;
                }
            }
        }
    }
    for (int len = 0; len < N; ++len) {
        for (int l = 0; l + len < N; ++l) {
            const int r = l + len;
            vector<vector<pair<int, int>>> buf(MAX * MAX + 1);
            if (len == 0) {
                for (int i = 0; i < H; ++i) {
                    for (int j = 0; j < W; ++j) {
                        if (grid[i][j] - '1' == l) {
                            dist[i][j][l][r] = 0;
                            buf[0].emplace_back(i, j);
                        }
                    }
                }
            } else {
                for (int i = 0; i < H; ++i) {
                    for (int j = 0; j < W; ++j) {
                        int min = INF;
                        for (int k = l; k < r; ++k) {
                            min = std::min(min, dist[i][j][l][k] + dist[i][j][k + 1][r]);
                        }
                        dist[i][j][l][r] = min;
                        if (min < MAX * MAX) {
                            buf[min].emplace_back(i, j);
                        }
                    }
                }
            }
            for (int d = 0; d < MAX * MAX; ++d) {
                for (const auto& [i, j] : buf[d]) {
                    for (int k = 0; k < 4; ++k) {
                        const auto [ni, nj] = dfs(i, j, k);
                        if (dist[ni][nj][l][r] > d + 1) {
                            dist[ni][nj][l][r] = d + 1;
                            buf[d + 1].emplace_back(ni, nj);
                        }
                    }
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            ans = std::min(ans, dist[i][j][0][N - 1]);
        }
    }
    std::cout << (ans == INF ? -1 : ans) << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6256 KB Output is correct
2 Correct 9 ms 6256 KB Output is correct
3 Correct 9 ms 6228 KB Output is correct
4 Correct 9 ms 6384 KB Output is correct
5 Correct 10 ms 6356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6256 KB Output is correct
2 Correct 9 ms 6256 KB Output is correct
3 Correct 9 ms 6228 KB Output is correct
4 Correct 9 ms 6384 KB Output is correct
5 Correct 10 ms 6356 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct
7 Correct 8 ms 6240 KB Output is correct
8 Correct 9 ms 6256 KB Output is correct
9 Correct 9 ms 6256 KB Output is correct
10 Correct 10 ms 6384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6256 KB Output is correct
2 Correct 9 ms 6256 KB Output is correct
3 Correct 9 ms 6228 KB Output is correct
4 Correct 9 ms 6384 KB Output is correct
5 Correct 10 ms 6356 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct
7 Correct 8 ms 6240 KB Output is correct
8 Correct 9 ms 6256 KB Output is correct
9 Correct 9 ms 6256 KB Output is correct
10 Correct 10 ms 6384 KB Output is correct
11 Correct 308 ms 42004 KB Output is correct
12 Correct 28 ms 41676 KB Output is correct
13 Correct 126 ms 42976 KB Output is correct
14 Correct 514 ms 42636 KB Output is correct
15 Correct 257 ms 41784 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6256 KB Output is correct
2 Correct 9 ms 6256 KB Output is correct
3 Correct 9 ms 6228 KB Output is correct
4 Correct 9 ms 6384 KB Output is correct
5 Correct 10 ms 6356 KB Output is correct
6 Correct 8 ms 6228 KB Output is correct
7 Correct 8 ms 6240 KB Output is correct
8 Correct 9 ms 6256 KB Output is correct
9 Correct 9 ms 6256 KB Output is correct
10 Correct 10 ms 6384 KB Output is correct
11 Correct 308 ms 42004 KB Output is correct
12 Correct 28 ms 41676 KB Output is correct
13 Correct 126 ms 42976 KB Output is correct
14 Correct 514 ms 42636 KB Output is correct
15 Correct 257 ms 41784 KB Output is correct
16 Correct 418 ms 98412 KB Output is correct
17 Correct 1375 ms 100340 KB Output is correct
18 Correct 547 ms 98216 KB Output is correct
19 Correct 457 ms 98388 KB Output is correct
20 Correct 1160 ms 98880 KB Output is correct