oj.uz

Submission #364646

# Submission time Handle Problem Language Result Execution time Memory
364646 2021-02-09T16:23:06 Z parsabahrami Robots (APIO13_robots) C++17
100 / 100
 1287 ms 117108 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 5e2 + 10, MOD = 1e9 + 7;
int M[N][N], shit[4][N][N], dp[10][10][N][N], n, m, k; pii G[4][N][N]; // wtf is this
char A[N][N]; int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

pii go(int x, int y, int d) {
    if (~G[d][x][y].F) return G[d][x][y];
    if (shit[d][x][y]) return G[d][x][y] = {-1, -1};
    int nxt = d;
    shit[d][x][y] = 1;
    if (A[x][y] == 'A') nxt = (nxt + 1) % 4;
    if (A[x][y] == 'C') nxt = (nxt - 1 + 4) % 4;
    int nx = dx[nxt] + x, ny = dy[nxt] + y;
    if (nx <= 0 || nx > n || ny > m || ny <= 0 || A[nx][ny] == 'x') return G[d][x][y] = {x, y};
    return G[d][x][y] = go(nx, ny, nxt);
}

int main() {
    for (int i = 0; i < 4; i++) 
        for (int j = 0; j < N; j++) 
            for (int l = 0; l < N; l++) G[i][j][l] = {-1, -1};
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", A[i] + 1);
    }
    for (int l = 0; l < 10; l++) 
        for (int r = 0; r < 10; r++) 
            for (int i = 0; i < N; i++) fill(dp[l][r][i], dp[l][r][i] + N, MOD);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i][j] != 'x') for (int d = 0; d < 4; d++) go(i, j, d);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i][j] != 'x' && A[i][j] != '.' && A[i][j] != 'A' && A[i][j] != 'C') dp[A[i][j] - '0'][A[i][j] - '0'][i][j] = 0;
        }
    }
    for (int sz = 1; sz <= k; sz++) {
        for (int l = 1; l + sz - 1 <= k; l++) {
            int r = l + sz - 1; deque<pii> q;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    for (int t = l; t < r; t++) dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][t][i][j] + dp[t + 1][r][i][j]);
                    if (dp[l][r][i][j] < MOD) q.push_back({i, j});
                }
            }
            sort(q.begin(), q.end(), [&] (pii x, pii y) { return dp[l][r][x.F][x.S] < dp[l][r][y.F][y.S]; });
            while (SZ(q)) {
                int x = q.front().F, y = q.front().S; q.pop_front();
                M[x][y] = 0;
                for (int d = 0; d < 4; d++) {
                    if (~G[d][x][y].F) {
                        int nx = G[d][x][y].F, ny = G[d][x][y].S;
                        if (dp[l][r][nx][ny] > dp[l][r][x][y] + 1) {
                            dp[l][r][nx][ny] = dp[l][r][x][y] + 1;
                            if (M[nx][ny]) continue;
                            M[nx][ny] = 1;
                            q.push_back({nx, ny});
                        }
                    }
                }
            }
        }
    }
    int ret = MOD;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) ret = min(ret, dp[1][k][i][j]);
    printf("%d\n", ret == MOD ? -1 : ret);
    return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     scanf("%d%d%d", &k, &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |         scanf("%s", A[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 110316 KB Output is correct
2 Correct 70 ms 110316 KB Output is correct
3 Correct 71 ms 110316 KB Output is correct
4 Correct 70 ms 110444 KB Output is correct
5 Correct 81 ms 110444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 110316 KB Output is correct
2 Correct 70 ms 110316 KB Output is correct
3 Correct 71 ms 110316 KB Output is correct
4 Correct 70 ms 110444 KB Output is correct
5 Correct 81 ms 110444 KB Output is correct
6 Correct 77 ms 110444 KB Output is correct
7 Correct 71 ms 110316 KB Output is correct
8 Correct 70 ms 110312 KB Output is correct
9 Correct 73 ms 110316 KB Output is correct
10 Correct 80 ms 110376 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 110316 KB Output is correct
2 Correct 70 ms 110316 KB Output is correct
3 Correct 71 ms 110316 KB Output is correct
4 Correct 70 ms 110444 KB Output is correct
5 Correct 81 ms 110444 KB Output is correct
6 Correct 77 ms 110444 KB Output is correct
7 Correct 71 ms 110316 KB Output is correct
8 Correct 70 ms 110312 KB Output is correct
9 Correct 73 ms 110316 KB Output is correct
10 Correct 80 ms 110376 KB Output is correct
11 Correct 190 ms 113900 KB Output is correct
12 Correct 79 ms 113516 KB Output is correct
13 Correct 99 ms 113132 KB Output is correct
14 Correct 469 ms 114148 KB Output is correct
15 Correct 139 ms 113644 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 110316 KB Output is correct
2 Correct 70 ms 110316 KB Output is correct
3 Correct 71 ms 110316 KB Output is correct
4 Correct 70 ms 110444 KB Output is correct
5 Correct 81 ms 110444 KB Output is correct
6 Correct 77 ms 110444 KB Output is correct
7 Correct 71 ms 110316 KB Output is correct
8 Correct 70 ms 110312 KB Output is correct
9 Correct 73 ms 110316 KB Output is correct
10 Correct 80 ms 110376 KB Output is correct
11 Correct 190 ms 113900 KB Output is correct
12 Correct 79 ms 113516 KB Output is correct
13 Correct 99 ms 113132 KB Output is correct
14 Correct 469 ms 114148 KB Output is correct
15 Correct 139 ms 113644 KB Output is correct
16 Correct 183 ms 115564 KB Output is correct
17 Correct 1287 ms 117108 KB Output is correct
18 Correct 241 ms 116332 KB Output is correct
19 Correct 178 ms 114796 KB Output is correct
20 Correct 659 ms 116588 KB Output is correct