oj.uz

Submission #630890

# Submission time Handle Problem Language Result Execution time Memory
630890 2022-08-17T10:04:05 Z MohamedFaresNebili Robots (APIO13_robots) C++14
30 / 100
 103 ms 158264 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[5][5][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 45 ms 63048 KB Output is correct
2 Correct 44 ms 63112 KB Output is correct
3 Correct 46 ms 63156 KB Output is correct
4 Correct 53 ms 63236 KB Output is correct
5 Correct 46 ms 63232 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 63048 KB Output is correct
2 Correct 44 ms 63112 KB Output is correct
3 Correct 46 ms 63156 KB Output is correct
4 Correct 53 ms 63236 KB Output is correct
5 Correct 46 ms 63232 KB Output is correct
6 Correct 46 ms 63148 KB Output is correct
7 Correct 45 ms 63076 KB Output is correct
8 Correct 44 ms 63060 KB Output is correct
9 Correct 44 ms 63172 KB Output is correct
10 Correct 53 ms 63140 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 63048 KB Output is correct
2 Correct 44 ms 63112 KB Output is correct
3 Correct 46 ms 63156 KB Output is correct
4 Correct 53 ms 63236 KB Output is correct
5 Correct 46 ms 63232 KB Output is correct
6 Correct 46 ms 63148 KB Output is correct
7 Correct 45 ms 63076 KB Output is correct
8 Correct 44 ms 63060 KB Output is correct
9 Correct 44 ms 63172 KB Output is correct
10 Correct 53 ms 63140 KB Output is correct
11 Runtime error 103 ms 158264 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 63048 KB Output is correct
2 Correct 44 ms 63112 KB Output is correct
3 Correct 46 ms 63156 KB Output is correct
4 Correct 53 ms 63236 KB Output is correct
5 Correct 46 ms 63232 KB Output is correct
6 Correct 46 ms 63148 KB Output is correct
7 Correct 45 ms 63076 KB Output is correct
8 Correct 44 ms 63060 KB Output is correct
9 Correct 44 ms 63172 KB Output is correct
10 Correct 53 ms 63140 KB Output is correct
11 Runtime error 103 ms 158264 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -