oj.uz

Submission #630911

# Submission time Handle Problem Language Result Execution time Memory
630911 2022-08-17T10:23:18 Z MohamedFaresNebili Robots (APIO13_robots) C++14
100 / 100
 645 ms 148212 KB 
#include <bits/stdc++.h>

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const int nx[4] = {-1, 0, 1, 0}, ny[4] = {0, 1, 0, -1};

            int N, W, H, D[45][500][500];
            vector<array<int, 2>> Q[2250005];
            array<int, 2> G[500][500][4];
            int Key[10][10];
            char grid[500][500];

            array<int, 2> dfs(int i, int j, int k) {
                if(G[i][j][k][0] != -1)
                    return G[i][j][k];
                int nxt = k;
                if(grid[i][j] == 'C') nxt = (nxt + 1) % 4;
                if(grid[i][j] == 'A') nxt = (nxt + 3) % 4;
                int x = i + nx[nxt], y = j + ny[nxt];
                if(x < 0 || y < 0 || x >= H || y >= W || grid[x][y] == 'x')
                    return G[i][j][k] = {i, j};
                return G[i][j][k] = dfs(x, y, nxt);
            }
            void update(int v, int x, int y, int d) {
                if(D[v][x][y] > d && d < 2250005) {
                    D[v][x][y] = d; Q[d].push_back({x, y});
                }
            }
            void solve(int v) {
                for(int l = 0; l < 2250005; l++) {
                    for(auto u : Q[l]) {
                        if(D[v][u[0]][u[1]] != l)
                            continue;
                        for(int k = 0; k < 4; k++) {
                            array<int, 2> arr = G[u[0]][u[1]][k];
                            update(v, arr[0], arr[1], l + 1);
                        }
                    }
                    Q[l].clear();
                }
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> W >> H;
                for(int l = 0; l < H; l++)
                    for(int i = 0; i < W; i++)
                        cin >> grid[l][i];
                memset(G, -1, sizeof G);
                for(int l = 0; l < H; l++)
                    for(int i = 0; i < W; i++) {
                        for(int j = 0; j < 4; j++)
                            dfs(l, i, j);
                    }
                for(int i = 0; i < 45; i++)
                    for(int x = 0; x < H; x++)
                        for(int y = 0; y < W; y++)
                            D[i][x][y] = 1e9 + 7;
                int cur = 0;
                for(int l = 0; l < N; l++) {
                    for(int i = l; ~i; i--) {
                        Key[i][l] = cur;
                        if(i < l) {
                            for(int x = 0; x < H; x++)
                                for(int y = 0; y < W; y++)
                                    for(int j = i; j < l; j++)
                                        update(cur, x, y, D[Key[i][j]][x][y] + D[Key[j + 1][l]][x][y]);
                        }
                        else {
                            for(int x = 0; x < H; x++)
                                for(int y = 0; y < W; y++) {
                                    int C = grid[x][y] - '0' - 1;
                                    if(C == l) update(cur, x, y, 0);
                                }
                        }
                        solve(cur++);
                    }
                }
                int res = 1e9 + 7;
                for(int l = 0; l < H; l++)
                    for(int i = 0; i < W; i++) {
                        res = min(res, D[Key[0][N - 1]][l][i]);
                    }
              	if(res == 1e9 + 7) res = -1;
                cout << res << "\n";
                return 0;
            }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 61124 KB Output is correct
2 Correct 41 ms 61248 KB Output is correct
3 Correct 38 ms 61244 KB Output is correct
4 Correct 38 ms 62036 KB Output is correct
5 Correct 44 ms 62028 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 61124 KB Output is correct
2 Correct 41 ms 61248 KB Output is correct
3 Correct 38 ms 61244 KB Output is correct
4 Correct 38 ms 62036 KB Output is correct
5 Correct 44 ms 62028 KB Output is correct
6 Correct 41 ms 61276 KB Output is correct
7 Correct 45 ms 61120 KB Output is correct
8 Correct 48 ms 61396 KB Output is correct
9 Correct 41 ms 61420 KB Output is correct
10 Correct 40 ms 61992 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 61124 KB Output is correct
2 Correct 41 ms 61248 KB Output is correct
3 Correct 38 ms 61244 KB Output is correct
4 Correct 38 ms 62036 KB Output is correct
5 Correct 44 ms 62028 KB Output is correct
6 Correct 41 ms 61276 KB Output is correct
7 Correct 45 ms 61120 KB Output is correct
8 Correct 48 ms 61396 KB Output is correct
9 Correct 41 ms 61420 KB Output is correct
10 Correct 40 ms 61992 KB Output is correct
11 Correct 294 ms 92160 KB Output is correct
12 Correct 49 ms 88020 KB Output is correct
13 Correct 169 ms 87744 KB Output is correct
14 Correct 358 ms 99580 KB Output is correct
15 Correct 289 ms 89036 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 61124 KB Output is correct
2 Correct 41 ms 61248 KB Output is correct
3 Correct 38 ms 61244 KB Output is correct
4 Correct 38 ms 62036 KB Output is correct
5 Correct 44 ms 62028 KB Output is correct
6 Correct 41 ms 61276 KB Output is correct
7 Correct 45 ms 61120 KB Output is correct
8 Correct 48 ms 61396 KB Output is correct
9 Correct 41 ms 61420 KB Output is correct
10 Correct 40 ms 61992 KB Output is correct
11 Correct 294 ms 92160 KB Output is correct
12 Correct 49 ms 88020 KB Output is correct
13 Correct 169 ms 87744 KB Output is correct
14 Correct 358 ms 99580 KB Output is correct
15 Correct 289 ms 89036 KB Output is correct
16 Correct 302 ms 105264 KB Output is correct
17 Correct 645 ms 148212 KB Output is correct
18 Correct 343 ms 109636 KB Output is correct
19 Correct 298 ms 105552 KB Output is correct
20 Correct 462 ms 122632 KB Output is correct