oj.uz

Submission #630891

# Submission time Handle Problem Language Result Execution time Memory
630891 2022-08-17T10:04:31 Z MohamedFaresNebili Robots (APIO13_robots) C++14
60 / 100
 437 ms 163840 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[10][10][505][505];
            vector<array<int, 2>> Q[2250005];
            array<int, 2> G[505][505][5];
            char grid[505][505];
 
            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 i, int j, int x, int y, int d) {
                if(D[i][j][x][y] > d && d < 2250005) {
                    D[i][j][x][y] = d; Q[d].push_back({x, y});
                }
            }
            void solve(int i, int j) {
                for(int l = 0; l < 2250005; l++) {
                    for(auto u : Q[l]) {
                        if(D[i][j][u[0]][u[1]] != l)
                            continue;
                        for(int k = 0; k < 4; k++) {
                            array<int, 2> arr = G[u[0]][u[1]][k];
                            update(i, j, 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 l = 0; l < N; l++)
                    for(int i = 0; i < N; i++)
                        for(int x = 0; x < H; x++)
                            for(int y = 0; y < W; y++)
                                D[l][i][x][y] = 1e9 + 7;
                for(int l = 0; l < N; l++) {
                    for(int i = l; ~i; i--) {
                        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(i, l, x, y, D[i][j][x][y] + D[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(l, l, x, y, 0);
                                }
                        }
                        solve(i, l);
                    }
                }
                int res = 1e9 + 7;
                for(int l = 0; l < H; l++)
                    for(int i = 0; i < W; i++) {
                        res = min(res, D[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 47 ms 63116 KB Output is correct
2 Correct 53 ms 63072 KB Output is correct
3 Correct 45 ms 63164 KB Output is correct
4 Correct 48 ms 63248 KB Output is correct
5 Correct 47 ms 63200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63116 KB Output is correct
2 Correct 53 ms 63072 KB Output is correct
3 Correct 45 ms 63164 KB Output is correct
4 Correct 48 ms 63248 KB Output is correct
5 Correct 47 ms 63200 KB Output is correct
6 Correct 45 ms 63156 KB Output is correct
7 Correct 47 ms 63092 KB Output is correct
8 Correct 45 ms 63044 KB Output is correct
9 Correct 55 ms 63060 KB Output is correct
10 Correct 46 ms 63188 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63116 KB Output is correct
2 Correct 53 ms 63072 KB Output is correct
3 Correct 45 ms 63164 KB Output is correct
4 Correct 48 ms 63248 KB Output is correct
5 Correct 47 ms 63200 KB Output is correct
6 Correct 45 ms 63156 KB Output is correct
7 Correct 47 ms 63092 KB Output is correct
8 Correct 45 ms 63044 KB Output is correct
9 Correct 55 ms 63060 KB Output is correct
10 Correct 46 ms 63188 KB Output is correct
11 Correct 355 ms 116184 KB Output is correct
12 Correct 44 ms 64460 KB Output is correct
13 Correct 215 ms 92748 KB Output is correct
14 Correct 437 ms 123468 KB Output is correct
15 Correct 354 ms 112836 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63116 KB Output is correct
2 Correct 53 ms 63072 KB Output is correct
3 Correct 45 ms 63164 KB Output is correct
4 Correct 48 ms 63248 KB Output is correct
5 Correct 47 ms 63200 KB Output is correct
6 Correct 45 ms 63156 KB Output is correct
7 Correct 47 ms 63092 KB Output is correct
8 Correct 45 ms 63044 KB Output is correct
9 Correct 55 ms 63060 KB Output is correct
10 Correct 46 ms 63188 KB Output is correct
11 Correct 355 ms 116184 KB Output is correct
12 Correct 44 ms 64460 KB Output is correct
13 Correct 215 ms 92748 KB Output is correct
14 Correct 437 ms 123468 KB Output is correct
15 Correct 354 ms 112836 KB Output is correct
16 Correct 361 ms 144048 KB Output is correct
17 Runtime error 297 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -