oj.uz

Submission #706737

# Submission time Handle Problem Language Result Execution time Memory
706737 2023-03-07T15:41:15 Z DennisTran Robots (APIO13_robots) C++17
100 / 100
 871 ms 146920 KB 
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define ii pair <int, int>
#define fi first
#define se second
using namespace std;

const int MAXN = 505;
const int INF = 250000;

int N, W, H, dp[MAXN][MAXN][10][10];
char a[MAXN][MAXN];
vector <ii> q[INF + 1];
ii end_pos[MAXN][MAXN][4];

inline bool inside(int x, int y) {
    return (x > 0 && y > 0 && x <= H && y <= W && a[x][y] != 'x');
}

void Find_ending_points(void) {
    FOR(i, 1, H) FOR(j, 1, W) if (a[i][j] != 'x') {
        REP(k, 4) {
            ii pos = {i, j};
            int d = (k + (a[i][j] == 'A') * 3 + (a[i][j] == 'C')) % 4;
 
            while (true) {
                if (d == 0) {
                    if (inside(pos.first - 1, pos.second)) pos.first--;
                    else break;
                } else if (d == 1) {
                    if (inside(pos.first, pos.second + 1)) pos.second++;
                    else break;
                } else if (d == 2) {
                    if (inside(pos.first + 1, pos.second)) pos.first++;
                    else break;
                } else {
                    if (inside(pos.first, pos.second - 1)) pos.second--;
                    else break;
                }
 
                if (~end_pos[pos.first][pos.second][d].first) {
                    pos = end_pos[pos.first][pos.second][d];
                    break;
                }
 
                if (a[pos.first][pos.second] == 'A') d = (d + 3) % 4;
                if (a[pos.first][pos.second] == 'C') d = (d + 1) % 4;
            }
 
            end_pos[i][j][k] = pos;
        }
    }
}

void solve(void) {
    memset(dp, 0x3f3f3f3f, sizeof dp);
    cin >> N >> W >> H;
    FOR(i, 1, H) FOR(j, 1, W) {
        cin >> a[i][j];
        if (a[i][j] >= '0' && a[i][j] <= '9') {
            dp[i][j][a[i][j] - '0'][a[i][j] - '0'] = 0;
        }
        REP(k, 4) end_pos[i][j][k] = {-1, -1};
    }
    Find_ending_points();


    REP(div, N) {
        FOR(l, 1, N - div) {
            int r = l + div;
            FOR(i, 1, H) FOR(j, 1, W) if (a[i][j] != 'x')
                for (int k = l; k < r; k++)
                    dp[i][j][l][r] = min(dp[i][j][l][r], dp[i][j][l][k]
                        + dp[i][j][k + 1][r]);
        }

        FOR(l, 1, N - div) {
            int r = l + div;
            FOR(i, 1, H) FOR(j, 1, W) if (a[i][j] != 'x' && dp[i][j][l][r] <= INF)
                q[dp[i][j][l][r]].emplace_back(i, j);

            FOR(i, 0, INF) if (q[i].size()) {
                for (auto tmp : q[i]) {
                    int x = tmp.fi, y = tmp.se;
                    if (dp[x][y][l][r] == i) {
                        REP(k, 4) {
                            int u = end_pos[x][y][k].first, v = end_pos[x][y][k].second;
                            if (dp[u][v][l][r] > dp[x][y][l][r] + 1) {
                                dp[u][v][l][r] = dp[x][y][l][r] + 1;
                                q[dp[u][v][l][r]].emplace_back(u, v);
                            }
                        }
                    }
                }
                q[i].clear();
            }
        }
    }

    int ans = INT_MAX;
    FOR(i, 1, H) FOR(j, 1, W) ans = min(ans, dp[i][j][1][N]);
    if (ans > INF) ans = -1;
    cout << ans;
}

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //int T; cin >> T; while (T--)  
    solve();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 105968 KB Output is correct
2 Correct 40 ms 105896 KB Output is correct
3 Correct 41 ms 105948 KB Output is correct
4 Correct 41 ms 106000 KB Output is correct
5 Correct 41 ms 105992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 105968 KB Output is correct
2 Correct 40 ms 105896 KB Output is correct
3 Correct 41 ms 105948 KB Output is correct
4 Correct 41 ms 106000 KB Output is correct
5 Correct 41 ms 105992 KB Output is correct
6 Correct 41 ms 106000 KB Output is correct
7 Correct 43 ms 105880 KB Output is correct
8 Correct 42 ms 106012 KB Output is correct
9 Correct 42 ms 106036 KB Output is correct
10 Correct 41 ms 106048 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 105968 KB Output is correct
2 Correct 40 ms 105896 KB Output is correct
3 Correct 41 ms 105948 KB Output is correct
4 Correct 41 ms 106000 KB Output is correct
5 Correct 41 ms 105992 KB Output is correct
6 Correct 41 ms 106000 KB Output is correct
7 Correct 43 ms 105880 KB Output is correct
8 Correct 42 ms 106012 KB Output is correct
9 Correct 42 ms 106036 KB Output is correct
10 Correct 41 ms 106048 KB Output is correct
11 Correct 205 ms 114072 KB Output is correct
12 Correct 49 ms 110628 KB Output is correct
13 Correct 126 ms 110284 KB Output is correct
14 Correct 288 ms 119268 KB Output is correct
15 Correct 168 ms 111388 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 105968 KB Output is correct
2 Correct 40 ms 105896 KB Output is correct
3 Correct 41 ms 105948 KB Output is correct
4 Correct 41 ms 106000 KB Output is correct
5 Correct 41 ms 105992 KB Output is correct
6 Correct 41 ms 106000 KB Output is correct
7 Correct 43 ms 105880 KB Output is correct
8 Correct 42 ms 106012 KB Output is correct
9 Correct 42 ms 106036 KB Output is correct
10 Correct 41 ms 106048 KB Output is correct
11 Correct 205 ms 114072 KB Output is correct
12 Correct 49 ms 110628 KB Output is correct
13 Correct 126 ms 110284 KB Output is correct
14 Correct 288 ms 119268 KB Output is correct
15 Correct 168 ms 111388 KB Output is correct
16 Correct 542 ms 114400 KB Output is correct
17 Correct 871 ms 146920 KB Output is correct
18 Correct 369 ms 118676 KB Output is correct
19 Correct 445 ms 114420 KB Output is correct
20 Correct 627 ms 129448 KB Output is correct