oj.uz

Submission #384730

# Submission time Handle Problem Language Result Execution time Memory
384730 2021-04-02T06:44:09 Z ParsaAlizadeh Robots (APIO13_robots) C++17
30 / 100
 1500 ms 83956 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_);
}

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];
        queue<int> q;
        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, q.push(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)
                    q.push(ij);
            }
        }
        while (!q.empty()) {
            int ij = q.front(); q.pop();
            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;
                    q.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 39 ms 83564 KB Output is correct
3 Correct 40 ms 83564 KB Output is correct
4 Correct 40 ms 83564 KB Output is correct
5 Correct 43 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 39 ms 83564 KB Output is correct
3 Correct 40 ms 83564 KB Output is correct
4 Correct 40 ms 83564 KB Output is correct
5 Correct 43 ms 83564 KB Output is correct
6 Correct 41 ms 83564 KB Output is correct
7 Correct 41 ms 83564 KB Output is correct
8 Correct 40 ms 83564 KB Output is correct
9 Correct 42 ms 83564 KB Output is correct
10 Correct 42 ms 83564 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83564 KB Output is correct
2 Correct 39 ms 83564 KB Output is correct
3 Correct 40 ms 83564 KB Output is correct
4 Correct 40 ms 83564 KB Output is correct
5 Correct 43 ms 83564 KB Output is correct
6 Correct 41 ms 83564 KB Output is correct
7 Correct 41 ms 83564 KB Output is correct
8 Correct 40 ms 83564 KB Output is correct
9 Correct 42 ms 83564 KB Output is correct
10 Correct 42 ms 83564 KB Output is correct
11 Execution timed out 1588 ms 83956 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 83564 KB Output is correct
2 Correct 39 ms 83564 KB Output is correct
3 Correct 40 ms 83564 KB Output is correct
4 Correct 40 ms 83564 KB Output is correct
5 Correct 43 ms 83564 KB Output is correct
6 Correct 41 ms 83564 KB Output is correct
7 Correct 41 ms 83564 KB Output is correct
8 Correct 40 ms 83564 KB Output is correct
9 Correct 42 ms 83564 KB Output is correct
10 Correct 42 ms 83564 KB Output is correct
11 Execution timed out 1588 ms 83956 KB Time limit exceeded
12 Halted 0 ms 0 KB -