oj.uz

Submission #384741

# Submission time Handle Problem Language Result Execution time Memory
384741 2021-04-02T06:52:05 Z ParsaAlizadeh Robots (APIO13_robots) C++17
100 / 100
 600 ms 85512 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          begin(x), end(x)
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'

constexpr int W   = 500;
constexpr int N   = 9;
constexpr int INF = W * W + 1;

int n, w, h, nxt[W * W][4], dp[N][N][W * W];
int dj[] = {+1, 0, -1, 0}, di[] = {0, -1, 0, +1};
char board[W][W];

int memoiz(int i, int j, int dir) {
    int ij = i * h + j;
    if (nxt[ij][dir] >= -1)
        return nxt[ij][dir];
    nxt[ij][dir] = -1;
    int dir_ = dir;
    if (board[i][j] == 'A')
        dir_ = (dir + 1) % 4;
    if (board[i][j] == 'C')
        dir_ = (dir + 3) % 4;
    int i_ = i + di[dir_], j_ = j + dj[dir_];
    if (i_ < 0 || i_ >= w || j_ < 0 || j_ >= h || board[i_][j_] == 'x')
        return nxt[ij][dir] = ij;
    return nxt[ij][dir] = memoiz(i_, j_, dir_);
}

inline int popitem(queue<int> & q) {
    int res = q.front(); q.pop();
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> h >> w;
    for (int i = 0; i < w; i++)
    for (int j = 0; j < h; j++)
        cin >> board[i][j];

    memset(nxt, 0x80, sizeof(nxt));
    for (int i = 0; i < w; i++)
    for (int j = 0; j < h; j++) {
        int ij = i * h + j;
        for (int dir : {0, 1, 2, 3})
            nxt[ij][dir] = board[i][j] == 'x' ? -1 : memoiz(i, j, dir);
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int r = 0; r < n; r++)
    for (int l = r; l >= 0; l--) {
        auto dp_ = dp[l][r];
        vector<int> vec;
        if (l == r) {
            for (int i = 0; i < w; i++)
            for (int j = 0; j < h; j++) {
                int ij = i * h + j;
                if (board[i][j] == l + '1')
                    dp_[ij] = 0, vec.push_back(ij);
            }
        }
        else {
            for (int i = 0; i < w; i++)
            for (int j = 0; j < h; j++) {
                int ij = i * h + j;
                for (int k = l; k < r; k++)
                    dp_[ij] = min(dp_[ij], dp[l][k][ij] + dp[k + 1][r][ij]);
                if (dp_[ij] < INF)
                    vec.push_back(ij);
            }
        }
        sort(all(vec), [&dp_] (int u, int v) {
            return dp_[u] < dp_[v];
        });
        queue<int> q1, q2;
        for (int u : vec)
            q1.push(u);
        while (!q1.empty() || !q2.empty()) {
            int ij = (q1.empty() || (!q2.empty() && dp_[q2.front()] < dp_[q1.front()]) ? popitem(q2) : popitem(q1));
            for (int dir : {0, 1, 2, 3}) {
                int v = nxt[ij][dir];
                if (v != -1 && dp_[v] > dp_[ij] + 1) {
                    dp_[v] = dp_[ij] + 1;
                    q2.push(v);
                }
            }
        }
    }

    int ans = *min_element(all(dp[0][n - 1]));
    cout << (ans < INF ? ans : -1) << endl;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83564 KB Output is correct
2 Correct 40 ms 83564 KB Output is correct
3 Correct 40 ms 83564 KB Output is correct
4 Correct 46 ms 83564 KB Output is correct
5 Correct 40 ms 83564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83564 KB Output is correct
2 Correct 40 ms 83564 KB Output is correct
3 Correct 40 ms 83564 KB Output is correct
4 Correct 46 ms 83564 KB Output is correct
5 Correct 40 ms 83564 KB Output is correct
6 Correct 42 ms 83456 KB Output is correct
7 Correct 45 ms 83564 KB Output is correct
8 Correct 41 ms 83564 KB Output is correct
9 Correct 44 ms 83564 KB Output is correct
10 Correct 40 ms 83564 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83564 KB Output is correct
2 Correct 40 ms 83564 KB Output is correct
3 Correct 40 ms 83564 KB Output is correct
4 Correct 46 ms 83564 KB Output is correct
5 Correct 40 ms 83564 KB Output is correct
6 Correct 42 ms 83456 KB Output is correct
7 Correct 45 ms 83564 KB Output is correct
8 Correct 41 ms 83564 KB Output is correct
9 Correct 44 ms 83564 KB Output is correct
10 Correct 40 ms 83564 KB Output is correct
11 Correct 128 ms 83948 KB Output is correct
12 Correct 46 ms 83692 KB Output is correct
13 Correct 70 ms 83692 KB Output is correct
14 Correct 245 ms 84396 KB Output is correct
15 Correct 108 ms 83820 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83564 KB Output is correct
2 Correct 40 ms 83564 KB Output is correct
3 Correct 40 ms 83564 KB Output is correct
4 Correct 46 ms 83564 KB Output is correct
5 Correct 40 ms 83564 KB Output is correct
6 Correct 42 ms 83456 KB Output is correct
7 Correct 45 ms 83564 KB Output is correct
8 Correct 41 ms 83564 KB Output is correct
9 Correct 44 ms 83564 KB Output is correct
10 Correct 40 ms 83564 KB Output is correct
11 Correct 128 ms 83948 KB Output is correct
12 Correct 46 ms 83692 KB Output is correct
13 Correct 70 ms 83692 KB Output is correct
14 Correct 245 ms 84396 KB Output is correct
15 Correct 108 ms 83820 KB Output is correct
16 Correct 208 ms 84204 KB Output is correct
17 Correct 600 ms 85512 KB Output is correct
18 Correct 225 ms 84552 KB Output is correct
19 Correct 202 ms 84076 KB Output is correct
20 Correct 447 ms 85184 KB Output is correct