oj.uz

Submission #726009

# Submission time Handle Problem Language Result Execution time Memory
726009 2023-04-18T10:05:54 Z vjudge1 Robots (APIO13_robots) C++17
60 / 100
 1500 ms 67124 KB 
#include <bits/stdc++.h>
using namespace std;

const int dr[] = {-1, 0, +1, 0};
const int dc[] = {0, +1, 0, -1};

enum {
        STAND = 4,
        UP = 0,
        RIGHT = 1,
        DOWN = 2,
        LEFT = 3,
        NOT_GOOD = 1000000000
};

int n, m, k;
char a[500][500];
int c[500][500];
int f[9][9][500][500];
int g[4][500][500];
vector<pair<int, int>> adj[500][500];

int DP(int z, int i, int j) {
        if (g[z][i][j] != -1) return g[z][i][j];
        g[z][i][j] = NOT_GOOD;
        int zz = (z + c[i][j]) % 4;
        int ii = i + dr[zz];
        int jj = j + dc[zz];
        if (ii < 0 || ii >= n || jj < 0 || jj >= m || a[ii][jj] == 'x') return g[z][i][j] = i * m + j;
        return g[z][i][j] = DP(zz, ii, jj);
}

int main() {
        cin >> k >> m >> n;
        for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++) cin >> a[i][j];
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                        for (int l = 0; l < k; l++)
                                for (int r = l; r < k; r++) f[l][r][i][j] = NOT_GOOD;
                        if (a[i][j] == 'A') {
                                c[i][j] = +3;
                        } else if (a[i][j] == 'C') {
                                c[i][j] = +1;
                        } else if (a[i][j] == 'x') {
                                c[i][j] = -1;
                        } else if (a[i][j] == '.') {
                                c[i][j] = 0;
                        } else {
                                a[i][j] -= '0' + 1;
                                assert(0 <= a[i][j] && a[i][j] < k);
                                f[a[i][j]][a[i][j]][i][j] = 0;
                        }
                }
        }

        memset(g, -1, sizeof g);

        for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                        if (a[i][j] == 'x') continue;
                        for (int z = 0; z < 4; z++) {
                                if (DP(z, i, j) == NOT_GOOD) continue;
                                int ii = DP(z, i, j) / m;
                                int jj = DP(z, i, j) % m;

                                adj[i][j].emplace_back(ii, jj);
                        }
                }
        }

        for (int r = 0; r < k; r++) {
                for (int l = r; l >= 0; l--) {
                        priority_queue<tuple<int, int, int>> pq;
                        for (int i = 0; i < n; i++) {
                                for (int j = 0; j < m; j++) {
                                        if (a[i][j] == 'x') continue;
                                        for (int mid = l; mid < r; mid++) f[l][r][i][j] = min(f[l][r][i][j], f[l][mid][i][j] + f[mid + 1][r][i][j]);
                                        if (f[l][r][i][j] != NOT_GOOD) pq.emplace(-f[l][r][i][j], i, j);
                                }
                        }
                        while (pq.size()) {
                                auto [d, i, j] = pq.top();
                                pq.pop();
                                d = -d;
                                if (f[l][r][i][j] != d) continue;
                                for (auto [ii, jj] : adj[i][j]) {
                                        if (f[l][r][ii][jj] > d + 1) {
                                                f[l][r][ii][jj] = d + 1;
                                                pq.emplace(-f[l][r][ii][jj], ii, jj);
                                        }
                                }
                        }
                }
        }

        int res = NOT_GOOD;
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                        if (a[i][j] != 'x') res = min(res, f[0][k - 1][i][j]);
                }
        }
        cout << (res == NOT_GOOD ? -1 : res);
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:52:41: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |                                 f[a[i][j]][a[i][j]][i][j] = 0;
      |                                   ~~~~~~^
robots.cpp:52:50: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |                                 f[a[i][j]][a[i][j]][i][j] = 0;
      |                                            ~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Correct 6 ms 10068 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 7 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Correct 6 ms 10068 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 7 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 5 ms 10068 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Correct 6 ms 10068 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 7 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 5 ms 10068 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct
11 Correct 140 ms 39892 KB Output is correct
12 Correct 19 ms 13412 KB Output is correct
13 Correct 37 ms 29576 KB Output is correct
14 Correct 566 ms 40888 KB Output is correct
15 Correct 91 ms 39752 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Correct 6 ms 10068 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 7 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 5 ms 10068 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct
11 Correct 140 ms 39892 KB Output is correct
12 Correct 19 ms 13412 KB Output is correct
13 Correct 37 ms 29576 KB Output is correct
14 Correct 566 ms 40888 KB Output is correct
15 Correct 91 ms 39752 KB Output is correct
16 Correct 159 ms 67124 KB Output is correct
17 Execution timed out 1578 ms 64552 KB Time limit exceeded
18 Halted 0 ms 0 KB -