oj.uz

Submission #422322

# Submission time Handle Problem Language Result Execution time Memory
422322 2021-06-10T03:08:06 Z SirCovidThe19th Robots (APIO13_robots) C++14
60 / 100
 1500 ms 97584 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]);
                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 37 ms 85444 KB Output is correct
2 Correct 36 ms 85336 KB Output is correct
3 Correct 39 ms 85412 KB Output is correct
4 Correct 36 ms 85520 KB Output is correct
5 Correct 44 ms 85580 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 36 ms 85336 KB Output is correct
3 Correct 39 ms 85412 KB Output is correct
4 Correct 36 ms 85520 KB Output is correct
5 Correct 44 ms 85580 KB Output is correct
6 Correct 36 ms 85452 KB Output is correct
7 Correct 43 ms 85416 KB Output is correct
8 Correct 46 ms 85452 KB Output is correct
9 Correct 43 ms 85444 KB Output is correct
10 Correct 38 ms 85516 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 36 ms 85336 KB Output is correct
3 Correct 39 ms 85412 KB Output is correct
4 Correct 36 ms 85520 KB Output is correct
5 Correct 44 ms 85580 KB Output is correct
6 Correct 36 ms 85452 KB Output is correct
7 Correct 43 ms 85416 KB Output is correct
8 Correct 46 ms 85452 KB Output is correct
9 Correct 43 ms 85444 KB Output is correct
10 Correct 38 ms 85516 KB Output is correct
11 Correct 254 ms 91260 KB Output is correct
12 Correct 50 ms 90180 KB Output is correct
13 Correct 96 ms 90388 KB Output is correct
14 Correct 571 ms 91696 KB Output is correct
15 Correct 181 ms 90760 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 85444 KB Output is correct
2 Correct 36 ms 85336 KB Output is correct
3 Correct 39 ms 85412 KB Output is correct
4 Correct 36 ms 85520 KB Output is correct
5 Correct 44 ms 85580 KB Output is correct
6 Correct 36 ms 85452 KB Output is correct
7 Correct 43 ms 85416 KB Output is correct
8 Correct 46 ms 85452 KB Output is correct
9 Correct 43 ms 85444 KB Output is correct
10 Correct 38 ms 85516 KB Output is correct
11 Correct 254 ms 91260 KB Output is correct
12 Correct 50 ms 90180 KB Output is correct
13 Correct 96 ms 90388 KB Output is correct
14 Correct 571 ms 91696 KB Output is correct
15 Correct 181 ms 90760 KB Output is correct
16 Correct 411 ms 93772 KB Output is correct
17 Execution timed out 1588 ms 97584 KB Time limit exceeded
18 Halted 0 ms 0 KB -