oj.uz

Submission #422329

# Submission time Handle Problem Language Result Execution time Memory
422329 2021-06-10T03:17:34 Z SirCovidThe19th Robots (APIO13_robots) C++14
100 / 100
 1101 ms 125928 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(){
    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 85344 KB Output is correct
2 Correct 37 ms 85452 KB Output is correct
3 Correct 38 ms 85364 KB Output is correct
4 Correct 37 ms 85576 KB Output is correct
5 Correct 38 ms 85496 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 85344 KB Output is correct
2 Correct 37 ms 85452 KB Output is correct
3 Correct 38 ms 85364 KB Output is correct
4 Correct 37 ms 85576 KB Output is correct
5 Correct 38 ms 85496 KB Output is correct
6 Correct 38 ms 85444 KB Output is correct
7 Correct 37 ms 85356 KB Output is correct
8 Correct 38 ms 85452 KB Output is correct
9 Correct 37 ms 85452 KB Output is correct
10 Correct 37 ms 85548 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 85344 KB Output is correct
2 Correct 37 ms 85452 KB Output is correct
3 Correct 38 ms 85364 KB Output is correct
4 Correct 37 ms 85576 KB Output is correct
5 Correct 38 ms 85496 KB Output is correct
6 Correct 38 ms 85444 KB Output is correct
7 Correct 37 ms 85356 KB Output is correct
8 Correct 38 ms 85452 KB Output is correct
9 Correct 37 ms 85452 KB Output is correct
10 Correct 37 ms 85548 KB Output is correct
11 Correct 189 ms 94060 KB Output is correct
12 Correct 59 ms 90712 KB Output is correct
13 Correct 105 ms 90276 KB Output is correct
14 Correct 345 ms 99276 KB Output is correct
15 Correct 156 ms 91332 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 85344 KB Output is correct
2 Correct 37 ms 85452 KB Output is correct
3 Correct 38 ms 85364 KB Output is correct
4 Correct 37 ms 85576 KB Output is correct
5 Correct 38 ms 85496 KB Output is correct
6 Correct 38 ms 85444 KB Output is correct
7 Correct 37 ms 85356 KB Output is correct
8 Correct 38 ms 85452 KB Output is correct
9 Correct 37 ms 85452 KB Output is correct
10 Correct 37 ms 85548 KB Output is correct
11 Correct 189 ms 94060 KB Output is correct
12 Correct 59 ms 90712 KB Output is correct
13 Correct 105 ms 90276 KB Output is correct
14 Correct 345 ms 99276 KB Output is correct
15 Correct 156 ms 91332 KB Output is correct
16 Correct 371 ms 93684 KB Output is correct
17 Correct 1101 ms 125928 KB Output is correct
18 Correct 471 ms 97728 KB Output is correct
19 Correct 312 ms 93600 KB Output is correct
20 Correct 802 ms 108376 KB Output is correct