oj.uz

Submission #422359

# Submission time Handle Problem Language Result Execution time Memory
422359 2021-06-10T04:40:41 Z SirCovidThe19th Robots (APIO13_robots) C++14
100 / 100
 1073 ms 126220 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 = mx*mx+1, 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(){
    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 38 ms 85452 KB Output is correct
2 Correct 40 ms 85328 KB Output is correct
3 Correct 37 ms 85440 KB Output is correct
4 Correct 44 ms 85524 KB Output is correct
5 Correct 36 ms 85532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85452 KB Output is correct
2 Correct 40 ms 85328 KB Output is correct
3 Correct 37 ms 85440 KB Output is correct
4 Correct 44 ms 85524 KB Output is correct
5 Correct 36 ms 85532 KB Output is correct
6 Correct 41 ms 85444 KB Output is correct
7 Correct 37 ms 85452 KB Output is correct
8 Correct 44 ms 85416 KB Output is correct
9 Correct 40 ms 85460 KB Output is correct
10 Correct 43 ms 85472 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85452 KB Output is correct
2 Correct 40 ms 85328 KB Output is correct
3 Correct 37 ms 85440 KB Output is correct
4 Correct 44 ms 85524 KB Output is correct
5 Correct 36 ms 85532 KB Output is correct
6 Correct 41 ms 85444 KB Output is correct
7 Correct 37 ms 85452 KB Output is correct
8 Correct 44 ms 85416 KB Output is correct
9 Correct 40 ms 85460 KB Output is correct
10 Correct 43 ms 85472 KB Output is correct
11 Correct 200 ms 94196 KB Output is correct
12 Correct 61 ms 90816 KB Output is correct
13 Correct 110 ms 90352 KB Output is correct
14 Correct 389 ms 99408 KB Output is correct
15 Correct 152 ms 91516 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85452 KB Output is correct
2 Correct 40 ms 85328 KB Output is correct
3 Correct 37 ms 85440 KB Output is correct
4 Correct 44 ms 85524 KB Output is correct
5 Correct 36 ms 85532 KB Output is correct
6 Correct 41 ms 85444 KB Output is correct
7 Correct 37 ms 85452 KB Output is correct
8 Correct 44 ms 85416 KB Output is correct
9 Correct 40 ms 85460 KB Output is correct
10 Correct 43 ms 85472 KB Output is correct
11 Correct 200 ms 94196 KB Output is correct
12 Correct 61 ms 90816 KB Output is correct
13 Correct 110 ms 90352 KB Output is correct
14 Correct 389 ms 99408 KB Output is correct
15 Correct 152 ms 91516 KB Output is correct
16 Correct 374 ms 93752 KB Output is correct
17 Correct 1073 ms 126220 KB Output is correct
18 Correct 396 ms 97900 KB Output is correct
19 Correct 305 ms 93764 KB Output is correct
20 Correct 780 ms 108816 KB Output is correct