oj.uz

Submission #469388

# Submission time Handle Problem Language Result Execution time Memory
469388 2021-08-31T18:09:41 Z chienyu_xiong Robots (APIO13_robots) C++17
60 / 100
 524 ms 163844 KB 
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

#define pb push_back
#define mp make_pair

#define int long long

#define pii pair<int, int>

#define all(_) begin(_), end(_)

#define smx(y, x) ((y) = max(x, y))
#define smn(y, x) ((y) = min(x, y))

void setIO() {
    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);
    cout.tie(nullptr);
}

const int N = 5e2 + 3;
const int M = 1e1 + 1;
const int K = 3e5 + 0;

const int inf = 9e17;
const int mod = 1e9 + 7; 

int xyz = 1; // test cases

int x, n, m;

int vis[N][N][4];
pii nxt[N][N][4];

int dp[N][N][M][M];

char grd[N][N];

vector<pii> que[K];

bool bnd(int y, int x) {
    return (y >= 0 && y < n) && (x >= 0 && x < m) && grd[y][x] != 'x';
}

pii dfs(int y, int x, int d) {
    if (grd[y][x] == 'A') d = (d + 3) % 4;
    if (grd[y][x] == 'C') d = (d + 1) % 4;

    if (vis[y][x][d])
        return nxt[y][x][d];

    vis[y][x][d] = 1;
    nxt[y][x][d] = {-1, -1};

    switch (d) {
        case 0: // N
            nxt[y][x][d] = bnd(y - 1, x) ? dfs(y - 1, x, d) : mp(y, x);
            break;
        case 1: // E
            nxt[y][x][d] = bnd(y, x + 1) ? dfs(y, x + 1, d) : mp(y, x);
            break;
        case 2: // S
            nxt[y][x][d] = bnd(y + 1, x) ? dfs(y + 1, x, d) : mp(y, x);
            break;
        case 3: // W
            nxt[y][x][d] = bnd(y, x - 1) ? dfs(y, x - 1, d) : mp(y, x);
            break;
        default: break;
    }

    return nxt[y][x][d];
}

void run() {
    cin >> x >> m >> n;

    for (int i = 0; i < n; i++)
        cin >> grd[i];

    for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
    for (int k = 0; k < 4; k++) {
        if (bnd(i, j)) dfs(i, j, k);
    }
    }
    }
    
    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    for (int r = 1; r <= x; r++)
    for (int l = 1; l <= x; l++)
        dp[i][j][l][r] = inf;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if ('1' <= grd[i][j] && grd[i][j] <= '9')
                dp[i][j][grd[i][j] - '0'][grd[i][j] - '0'] = 0;

    /* for (int i = 0; i < n; i++) */
    /*     for (int j = 0; j < m; j++) */
    /*         for (int k = 0; k < 4; k++) */
    /*             cout << i << " " << j << " " << k << ": " << nxt[i][j][k].F << " | " << nxt[i][j][k].S << endl; */

    for (int w = 0; w < x; w++) {
        for (int v = 1; v + w <= x; v++) {
            int l = v;
            int r = v + w;

            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    for (int k = l; k < r; k++)
                        smn(dp[i][j][l][r], dp[i][j][l][k + 0] + dp[i][j][k + 1][r]);
        }

        for (int v = 1; v + w <= x; v++) {
            int l = v;
            int r = v + w;

            for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (dp[i][j][l][r] < K)
                    que[dp[i][j][l][r]].pb({i, j});

            for (int d = 0; d < K; d++) {
                for (auto [y, x] : que[d]) {
                    if (dp[y][x][l][r] != d) continue;

                    for (int k = 0; k < 4; k++) {
                        int ny;
                        int nx;
                        tie(ny, nx) = nxt[y][x][k];

                        int val = d + 1;
                        if (bnd(ny, nx) && dp[ny][nx][l][r] > val && val < K)
                            que[dp[ny][nx][l][r] = val].pb({ny, nx});
                    }
                }
                que[d].clear();
            }
        }
    }

    int ans = inf;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            smn(ans, dp[i][j][1][x]);
        }
    }

    cout << (ans == inf ? -1 : ans) << endl;
}

signed main() {
    setIO();

    while (xyz--)
        run();

#ifdef LOCAL
    cin.clear(); cout.flush(); system("pause");
#endif

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 7 ms 7372 KB Output is correct
3 Correct 7 ms 7372 KB Output is correct
4 Correct 7 ms 7500 KB Output is correct
5 Correct 8 ms 7500 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 7 ms 7372 KB Output is correct
3 Correct 7 ms 7372 KB Output is correct
4 Correct 7 ms 7500 KB Output is correct
5 Correct 8 ms 7500 KB Output is correct
6 Correct 8 ms 7372 KB Output is correct
7 Correct 7 ms 7372 KB Output is correct
8 Correct 8 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 8 ms 7616 KB Output is correct
11 Correct 343 ms 107192 KB Output is correct
12 Correct 49 ms 100956 KB Output is correct
13 Correct 163 ms 104768 KB Output is correct
14 Correct 524 ms 117812 KB Output is correct
15 Correct 278 ms 102512 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 7 ms 7372 KB Output is correct
3 Correct 7 ms 7372 KB Output is correct
4 Correct 7 ms 7500 KB Output is correct
5 Correct 8 ms 7500 KB Output is correct
6 Correct 8 ms 7372 KB Output is correct
7 Correct 7 ms 7372 KB Output is correct
8 Correct 8 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 8 ms 7616 KB Output is correct
11 Correct 343 ms 107192 KB Output is correct
12 Correct 49 ms 100956 KB Output is correct
13 Correct 163 ms 104768 KB Output is correct
14 Correct 524 ms 117812 KB Output is correct
15 Correct 278 ms 102512 KB Output is correct
16 Runtime error 96 ms 163844 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -