oj.uz

Submission #422328

# Submission time Handle Problem Language Result Execution time Memory
422328 2021-06-10T03:17:06 Z SirCovidThe19th Robots (APIO13_robots) C++14
100 / 100
 1058 ms 125936 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, x, y) for (int i = x; i < y; i++)

const int mx = 500;

int n, w, h, ans = 505*505, dp[mx][mx][9][9], di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1}; 
char grid[mx][mx]; pair<int, int> pos[4][mx][mx]; vector<pair<int, int>> trav[mx*mx];

pair<int, int> nextPos(int i, int j, int d){
    int old = d; d = (d-(grid[i][j] == 'A')+(grid[i][j] == 'C')+4)%4;
    int r = i+di[d], c = j+dj[d]; pos[old][i][j] = {-2, -2}; pair<int, int> ret;
    if (!(r < h and r >= 0 and c < w and c >= 0 and grid[r][c] != 'x')) ret = {i, j};
    else if (pos[d][r][c] != make_pair(-1, -1)) ret = pos[d][r][c];
    else ret = nextPos(r, c, d);
    return pos[old][i][j] = ret;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    cin >> n >> w >> h; memset(dp, 0x3f, sizeof(dp));
    FOR(i, 0, h) FOR(j, 0, w) { cin >> grid[i][j]; if (isdigit(grid[i][j])) dp[i][j][grid[i][j]-'1'][grid[i][j]-'1'] = 0; }
    FOR(i, 0, h) FOR(j, 0, w) FOR(d, 0, 4) pos[d][i][j] = {-1, -1};
    FOR(i, 0, h) FOR(j, 0, w) FOR(d, 0, 4) if (grid[i][j] != 'x') nextPos(i, j, d);
    FOR(l, 0, n){
        FOR(x, 0, n-l){
            int y = x+l; 
            FOR(i, 0, h) FOR(j, 0, w) if (grid[i][j] != 'x'){
                FOR(mid, x, y)
                    dp[i][j][x][y] = min(dp[i][j][x][y], dp[i][j][x][mid]+dp[i][j][mid+1][y]);
                if (dp[i][j][x][y] < w*h) trav[dp[i][j][x][y]].push_back({i, j});
            }
            FOR(i, 0, w*h){
                for (pair<int, int> curr : trav[i]){
                    int r = curr.first, c = curr.second;
                    FOR(d, 0, 4){
                        int r1, c1; tie(r1, c1) = pos[d][r][c]; 
                        if (r1 < 0 or c1 < 0) continue;
                        if (dp[r][c][x][y]+1 < dp[r1][c1][x][y]){
                            dp[r1][c1][x][y] = dp[r][c][x][y]+1;
                            trav[dp[r1][c1][x][y]].push_back({r1, c1});
                        }
                    }
                }
                trav[i].clear();
            }
        }
    }
    FOR(i, 0, h) FOR(j, 0, w) ans = min(ans, dp[i][j][0][n-1]);
    cout<<((ans > w*h) ? -1 : ans);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 85444 KB Output is correct
2 Correct 44 ms 85428 KB Output is correct
3 Correct 37 ms 85384 KB Output is correct
4 Correct 38 ms 85572 KB Output is correct
5 Correct 37 ms 85544 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 85444 KB Output is correct
2 Correct 44 ms 85428 KB Output is correct
3 Correct 37 ms 85384 KB Output is correct
4 Correct 38 ms 85572 KB Output is correct
5 Correct 37 ms 85544 KB Output is correct
6 Correct 36 ms 85396 KB Output is correct
7 Correct 37 ms 85408 KB Output is correct
8 Correct 39 ms 85464 KB Output is correct
9 Correct 38 ms 85404 KB Output is correct
10 Correct 44 ms 85492 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 85444 KB Output is correct
2 Correct 44 ms 85428 KB Output is correct
3 Correct 37 ms 85384 KB Output is correct
4 Correct 38 ms 85572 KB Output is correct
5 Correct 37 ms 85544 KB Output is correct
6 Correct 36 ms 85396 KB Output is correct
7 Correct 37 ms 85408 KB Output is correct
8 Correct 39 ms 85464 KB Output is correct
9 Correct 38 ms 85404 KB Output is correct
10 Correct 44 ms 85492 KB Output is correct
11 Correct 202 ms 94256 KB Output is correct
12 Correct 50 ms 90856 KB Output is correct
13 Correct 101 ms 90312 KB Output is correct
14 Correct 363 ms 99336 KB Output is correct
15 Correct 147 ms 91460 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 85444 KB Output is correct
2 Correct 44 ms 85428 KB Output is correct
3 Correct 37 ms 85384 KB Output is correct
4 Correct 38 ms 85572 KB Output is correct
5 Correct 37 ms 85544 KB Output is correct
6 Correct 36 ms 85396 KB Output is correct
7 Correct 37 ms 85408 KB Output is correct
8 Correct 39 ms 85464 KB Output is correct
9 Correct 38 ms 85404 KB Output is correct
10 Correct 44 ms 85492 KB Output is correct
11 Correct 202 ms 94256 KB Output is correct
12 Correct 50 ms 90856 KB Output is correct
13 Correct 101 ms 90312 KB Output is correct
14 Correct 363 ms 99336 KB Output is correct
15 Correct 147 ms 91460 KB Output is correct
16 Correct 373 ms 93528 KB Output is correct
17 Correct 1058 ms 125936 KB Output is correct
18 Correct 371 ms 97804 KB Output is correct
19 Correct 302 ms 93816 KB Output is correct
20 Correct 790 ms 108644 KB Output is correct