oj.uz

Submission #469389

# Submission time Handle Problem Language Result Execution time Memory
469389 2021-08-31T18:14:00 Z chienyu_xiong Robots (APIO13_robots) C++17
60 / 100
 515 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];

string grd[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 7356 KB Output is correct
3 Correct 8 ms 7284 KB Output is correct
4 Correct 7 ms 7628 KB Output is correct
5 Correct 10 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 7356 KB Output is correct
3 Correct 8 ms 7284 KB Output is correct
4 Correct 7 ms 7628 KB Output is correct
5 Correct 10 ms 7500 KB Output is correct
6 Correct 7 ms 7360 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 7 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 7 ms 7500 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 7356 KB Output is correct
3 Correct 8 ms 7284 KB Output is correct
4 Correct 7 ms 7628 KB Output is correct
5 Correct 10 ms 7500 KB Output is correct
6 Correct 7 ms 7360 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 7 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 7 ms 7500 KB Output is correct
11 Correct 319 ms 107272 KB Output is correct
12 Correct 49 ms 100932 KB Output is correct
13 Correct 158 ms 104796 KB Output is correct
14 Correct 515 ms 117620 KB Output is correct
15 Correct 272 ms 102372 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 7356 KB Output is correct
3 Correct 8 ms 7284 KB Output is correct
4 Correct 7 ms 7628 KB Output is correct
5 Correct 10 ms 7500 KB Output is correct
6 Correct 7 ms 7360 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 7 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 7 ms 7500 KB Output is correct
11 Correct 319 ms 107272 KB Output is correct
12 Correct 49 ms 100932 KB Output is correct
13 Correct 158 ms 104796 KB Output is correct
14 Correct 515 ms 117620 KB Output is correct
15 Correct 272 ms 102372 KB Output is correct
16 Runtime error 98 ms 163844 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -