oj.uz

Submission #726025

# Submission time Handle Problem Language Result Execution time Memory
726025 2023-04-18T10:18:13 Z vjudge1 Robots (APIO13_robots) C++17
100 / 100
 511 ms 67020 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);
}

class data_t {
       public:
        int d, i, j;
        data_t(int d, int i, int j) : d(d), i(i), j(j) {}

        bool operator<(const data_t& other) const {
                return d > other.d;
        }
};

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--) {
                        vector<data_t> best;
                        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) best.emplace_back(f[l][r][i][j], i, j);
                                }
                        }
                        sort(best.begin(), best.end());
                        deque<data_t> q;
                        while (best.size() || q.size()) {
                                if (q.empty() || (best.size() && best.back().d <= q.front().d)) q.emplace_front(best.back()), best.pop_back();
                                data_t cur = q.front();
                                q.pop_front();
                                if (f[l][r][cur.i][cur.j] != cur.d) continue;
                                for (auto [ii, jj] : adj[cur.i][cur.j]) {
                                        if (f[l][r][ii][jj] > cur.d + 1) {
                                                f[l][r][ii][jj] = cur.d + 1;
                                                q.emplace_back(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:62:41: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |                                 f[a[i][j]][a[i][j]][i][j] = 0;
      |                                   ~~~~~~^
robots.cpp:62:50: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |                                 f[a[i][j]][a[i][j]][i][j] = 0;
      |                                            ~~~~~~^

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10068 KB Output is correct
2 Correct 6 ms 10028 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 5 ms 10196 KB Output is correct
5 Correct 6 ms 10196 KB Output is correct
6 Correct 6 ms 10016 KB Output is correct
7 Correct 7 ms 10016 KB Output is correct
8 Correct 7 ms 10068 KB Output is correct
9 Correct 7 ms 10080 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 88 ms 40000 KB Output is correct
12 Correct 20 ms 13524 KB Output is correct
13 Correct 36 ms 29568 KB Output is correct
14 Correct 217 ms 40756 KB Output is correct
15 Correct 56 ms 39732 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10068 KB Output is correct
2 Correct 6 ms 10028 KB Output is correct
3 Correct 5 ms 10068 KB Output is correct
4 Correct 5 ms 10196 KB Output is correct
5 Correct 6 ms 10196 KB Output is correct
6 Correct 6 ms 10016 KB Output is correct
7 Correct 7 ms 10016 KB Output is correct
8 Correct 7 ms 10068 KB Output is correct
9 Correct 7 ms 10080 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 88 ms 40000 KB Output is correct
12 Correct 20 ms 13524 KB Output is correct
13 Correct 36 ms 29568 KB Output is correct
14 Correct 217 ms 40756 KB Output is correct
15 Correct 56 ms 39732 KB Output is correct
16 Correct 141 ms 67020 KB Output is correct
17 Correct 511 ms 64524 KB Output is correct
18 Correct 128 ms 62880 KB Output is correct
19 Correct 102 ms 61516 KB Output is correct
20 Correct 357 ms 63932 KB Output is correct