oj.uz

Submission #630916

# Submission time Handle Problem Language Result Execution time Memory
630916 2022-08-17T10:25:52 Z MohamedFaresNebili Robots (APIO13_robots) C++14
100 / 100
 388 ms 101012 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

            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};
            const int MX = 250000;

            int N, W, H, D[45][500][500];
            vector<array<int, 2>> Q[MX];
            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 < MX) {
                    D[v][x][y] = d; Q[d].push_back({x, y});
                }
            }
            void solve(int v) {
                for(int l = 0; l < MX; 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 8 ms 14292 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 8 ms 14212 KB Output is correct
4 Correct 10 ms 15080 KB Output is correct
5 Correct 8 ms 15060 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 8 ms 14212 KB Output is correct
4 Correct 10 ms 15080 KB Output is correct
5 Correct 8 ms 15060 KB Output is correct
6 Correct 8 ms 14272 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 8 ms 14352 KB Output is correct
9 Correct 11 ms 14376 KB Output is correct
10 Correct 11 ms 15088 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 8 ms 14212 KB Output is correct
4 Correct 10 ms 15080 KB Output is correct
5 Correct 8 ms 15060 KB Output is correct
6 Correct 8 ms 14272 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 8 ms 14352 KB Output is correct
9 Correct 11 ms 14376 KB Output is correct
10 Correct 11 ms 15088 KB Output is correct
11 Correct 84 ms 45240 KB Output is correct
12 Correct 20 ms 41048 KB Output is correct
13 Correct 43 ms 40796 KB Output is correct
14 Correct 157 ms 52688 KB Output is correct
15 Correct 73 ms 42024 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 8 ms 14212 KB Output is correct
4 Correct 10 ms 15080 KB Output is correct
5 Correct 8 ms 15060 KB Output is correct
6 Correct 8 ms 14272 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 8 ms 14352 KB Output is correct
9 Correct 11 ms 14376 KB Output is correct
10 Correct 11 ms 15088 KB Output is correct
11 Correct 84 ms 45240 KB Output is correct
12 Correct 20 ms 41048 KB Output is correct
13 Correct 43 ms 40796 KB Output is correct
14 Correct 157 ms 52688 KB Output is correct
15 Correct 73 ms 42024 KB Output is correct
16 Correct 111 ms 58304 KB Output is correct
17 Correct 388 ms 101012 KB Output is correct
18 Correct 124 ms 62344 KB Output is correct
19 Correct 109 ms 58316 KB Output is correct
20 Correct 220 ms 75440 KB Output is correct