oj.uz

Submission #422318

# Submission time Handle Problem Language Result Execution time Memory
422318 2021-06-10T02:56:49 Z SirCovidThe19th Robots (APIO13_robots) C++14
60 / 100
 1500 ms 97336 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]; list<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]);
            FOR(i, 0, h) FOR(j, 0, w) if (dp[i][j][x][y] < w*h) trav[dp[i][j][x][y]].push_back({i, j});
            FOR(i, 0, w*h){
                while (!trav[i].empty()){
                    int r, c; tie(r, c) = trav[i].front(); trav[i].pop_front();
                    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});
                        }
                    }
                }
            }
        }
    }
    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 85368 KB Output is correct
2 Correct 39 ms 85412 KB Output is correct
3 Correct 40 ms 85428 KB Output is correct
4 Correct 42 ms 85484 KB Output is correct
5 Correct 39 ms 85516 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85368 KB Output is correct
2 Correct 39 ms 85412 KB Output is correct
3 Correct 40 ms 85428 KB Output is correct
4 Correct 42 ms 85484 KB Output is correct
5 Correct 39 ms 85516 KB Output is correct
6 Correct 40 ms 85400 KB Output is correct
7 Correct 43 ms 85384 KB Output is correct
8 Correct 41 ms 85472 KB Output is correct
9 Correct 40 ms 85464 KB Output is correct
10 Correct 38 ms 85604 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85368 KB Output is correct
2 Correct 39 ms 85412 KB Output is correct
3 Correct 40 ms 85428 KB Output is correct
4 Correct 42 ms 85484 KB Output is correct
5 Correct 39 ms 85516 KB Output is correct
6 Correct 40 ms 85400 KB Output is correct
7 Correct 43 ms 85384 KB Output is correct
8 Correct 41 ms 85472 KB Output is correct
9 Correct 40 ms 85464 KB Output is correct
10 Correct 38 ms 85604 KB Output is correct
11 Correct 284 ms 91144 KB Output is correct
12 Correct 57 ms 90148 KB Output is correct
13 Correct 116 ms 90420 KB Output is correct
14 Correct 524 ms 91604 KB Output is correct
15 Correct 191 ms 90696 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85368 KB Output is correct
2 Correct 39 ms 85412 KB Output is correct
3 Correct 40 ms 85428 KB Output is correct
4 Correct 42 ms 85484 KB Output is correct
5 Correct 39 ms 85516 KB Output is correct
6 Correct 40 ms 85400 KB Output is correct
7 Correct 43 ms 85384 KB Output is correct
8 Correct 41 ms 85472 KB Output is correct
9 Correct 40 ms 85464 KB Output is correct
10 Correct 38 ms 85604 KB Output is correct
11 Correct 284 ms 91144 KB Output is correct
12 Correct 57 ms 90148 KB Output is correct
13 Correct 116 ms 90420 KB Output is correct
14 Correct 524 ms 91604 KB Output is correct
15 Correct 191 ms 90696 KB Output is correct
16 Correct 418 ms 93480 KB Output is correct
17 Execution timed out 1589 ms 97336 KB Time limit exceeded
18 Halted 0 ms 0 KB -