oj.uz

Submission #630893

# Submission time Handle Problem Language Result Execution time Memory
630893 2022-08-17T10:05:23 Z MohamedFaresNebili Robots (APIO13_robots) C++14
60 / 100
 366 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[9][9][500][500];
            vector<array<int, 2>> Q[2250005];
            array<int, 2> G[500][500][4];
            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 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 44 ms 60964 KB Output is correct
2 Correct 39 ms 60956 KB Output is correct
3 Correct 41 ms 61012 KB Output is correct
4 Correct 43 ms 61076 KB Output is correct
5 Correct 43 ms 60960 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 60964 KB Output is correct
2 Correct 39 ms 60956 KB Output is correct
3 Correct 41 ms 61012 KB Output is correct
4 Correct 43 ms 61076 KB Output is correct
5 Correct 43 ms 60960 KB Output is correct
6 Correct 40 ms 61004 KB Output is correct
7 Correct 43 ms 60996 KB Output is correct
8 Correct 44 ms 61012 KB Output is correct
9 Correct 39 ms 60996 KB Output is correct
10 Correct 40 ms 61012 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 60964 KB Output is correct
2 Correct 39 ms 60956 KB Output is correct
3 Correct 41 ms 61012 KB Output is correct
4 Correct 43 ms 61076 KB Output is correct
5 Correct 43 ms 60960 KB Output is correct
6 Correct 40 ms 61004 KB Output is correct
7 Correct 43 ms 60996 KB Output is correct
8 Correct 44 ms 61012 KB Output is correct
9 Correct 39 ms 60996 KB Output is correct
10 Correct 40 ms 61012 KB Output is correct
11 Correct 295 ms 113432 KB Output is correct
12 Correct 37 ms 62164 KB Output is correct
13 Correct 162 ms 90064 KB Output is correct
14 Correct 366 ms 120872 KB Output is correct
15 Correct 253 ms 110148 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 60964 KB Output is correct
2 Correct 39 ms 60956 KB Output is correct
3 Correct 41 ms 61012 KB Output is correct
4 Correct 43 ms 61076 KB Output is correct
5 Correct 43 ms 60960 KB Output is correct
6 Correct 40 ms 61004 KB Output is correct
7 Correct 43 ms 60996 KB Output is correct
8 Correct 44 ms 61012 KB Output is correct
9 Correct 39 ms 60996 KB Output is correct
10 Correct 40 ms 61012 KB Output is correct
11 Correct 295 ms 113432 KB Output is correct
12 Correct 37 ms 62164 KB Output is correct
13 Correct 162 ms 90064 KB Output is correct
14 Correct 366 ms 120872 KB Output is correct
15 Correct 253 ms 110148 KB Output is correct
16 Correct 291 ms 140496 KB Output is correct
17 Runtime error 287 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -