oj.uz

Submission #122131

# Submission time Handle Problem Language Result Execution time Memory
122131 2019-06-27T16:13:53 Z jakob_nogler Robots (APIO13_robots) C++14
60 / 100
 596 ms 163840 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
    
using namespace std;
    
typedef short int si;
typedef pair<si, si> pii;
typedef tuple<si, si, si> tiii;
typedef tuple<si, si, si, si> tiiii;
    
const int N = 355, dir = 4, R = 9, inf = 10e8, sum = R * (R + 1) / 2;
    
pii nxt[N][N][dir];
int cost[R][N][N], dp[sum][N][N], dict[R][R];
char grid[N][N];
int n, w, h;
    
int dr[dir] = {1, 0, - 1, 0};
int dc[dir] = {0, 1, 0, - 1}; //down, right, up, left
    
queue<tiiii> q3[N * N];
    
int main(){
    cin >> n >> w >> h;
    w += 2; h += 2;
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++){
            grid[i][j] = 'x';
            for(int k = 0; k < dir; k++)
                nxt[i][j][k] = {- 1, - 1};
            for(int k = 0; k < n; k++)
                cost[k][i][j] = - 1;
            for(int k = 0; k < sum; k++)
                dp[k][i][j] = inf;
        }

    int idx = 0;
    for(int i = 0; i < R; i++)
        for(int j = i; j < R; j++)
            dict[i][j] = idx++;
    
    queue<tiii> q0, q1;
    for(int i = 1; i < h - 1; i++)
        for(int j = 1; j < w - 1; j++){
            cin >> grid[i][j];
            if(grid[i][j] >= '1' && grid[i][j] <= '9'){
                cost[grid[i][j] - '1'][i][j] = 0;
                q1.push({grid[i][j] - '1', i, j});
            }
        }
    
    for(int i = 1; i < h - 1; i++)
        for(int j = 1; j < w - 1; j++)
            for(int k = 0; k < dir; k++)
                if(grid[i][j] != 'x' && grid[i + dr[k]][j + dc[k]] == 'x'){
                    q0.push({i, j, k});
                    nxt[i][j][k] = {i, j};
                }
    
    while(!q0.empty()){
        tiii curr = q0.front();
        q0.pop();
        int d = get<2>(curr), id, mov;
        pii pos = {get<0>(curr), get<1>(curr)};
    
        if(grid[pos.fi][pos.se] == 'A') mov = (d + 1) % 4, id = (d + 3) % 4;
        else if(grid[pos.fi][pos.se] == 'C') mov = (d + 3) % 4, id = (d + 1) % 4;
        else mov = (d + 2) % 4, id = d;
        if(grid[pos.fi + dr[mov]][pos.se + dc[mov]] == 'x') continue;
        nxt[pos.fi + dr[mov]][pos.se + dc[mov]][id] = nxt[pos.fi][pos.se][d];
        q0.push({pos.fi + dr[mov], pos.se + dc[mov], id});
    }
    
    while(!q1.empty()){
        tiii curr = q1.front();
        q1.pop();
        int r = get<0>(curr);
        pii pos = {get<1>(curr), get<2>(curr)};
    
        dp[dict[r][r]][pos.fi][pos.se] = cost[r][pos.fi][pos.se];
        q3[cost[r][pos.fi][pos.se]].push({r, r, pos.fi, pos.se});
    
        for(int i = 0; i < dir; i++){
            pii nn = nxt[pos.fi][pos.se][i];
            if(cost[r][nn.fi][nn.se] == - 1){
                cost[r][nn.fi][nn.se] = cost[r][pos.fi][pos.se] + 1;
                q1.push({r, nn.fi, nn.se});
            }
        }
    }
    
    for(int v = 0; v < N * N; v++){
        while(!q3[v].empty()){
            tiiii curr = q3[v].front();
            q3[v].pop();
    
            int lo = get<0>(curr), hi = get<1>(curr);
            pii pos = {get<2>(curr), get<3>(curr)};

            if(lo == 0 && hi == n - 1){
                cout << v << endl;
                return 0;
            }
    
            if(dp[dict[lo][hi]][pos.fi][pos.se] < v) continue;
            for(int i = hi + 1; i < n; i++)
                if(dp[dict[lo][i]][pos.fi][pos.se] > dp[dict[hi + 1][i]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se]){
                    dp[dict[lo][i]][pos.fi][pos.se] = dp[dict[hi + 1][i]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se];
                    q3[dp[dict[lo][i]][pos.fi][pos.se]].push({lo, i, pos.fi, pos.se});
                }
            for(int i = lo - 1; i >= 0; i--)
                if(dp[dict[i][hi]][pos.fi][pos.se] > dp[dict[i][lo - 1]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se]){
                    dp[dict[i][hi]][pos.fi][pos.se] = dp[dict[i][lo - 1]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se];
                    q3[dp[dict[i][hi]][pos.fi][pos.se]].push({i, hi, pos.fi, pos.se});
                }
    
            for(int i = 0; i < dir; i++){
                pii nn = nxt[pos.fi][pos.se][i];
                if(dp[dict[lo][hi]][nn.fi][nn.se] > dp[dict[lo][hi]][pos.fi][pos.se] + 1){
                    dp[dict[lo][hi]][nn.fi][nn.se] = dp[dict[lo][hi]][pos.fi][pos.se] + 1;
                    q3[dp[dict[lo][hi]][nn.fi][nn.se]].push({lo, hi, nn.fi, nn.se});
                }
            }
        }
    }
    
    int ans = inf;
    for(int i = 1; i < h - 1; i++)
        for(int j = 1; j < w - 1; j++)
            ans = min(ans, dp[dict[0][n - 1]][i][j]);
    
    if(ans == inf) cout << - 1 << endl;
    else cout << ans << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 85496 KB Output is correct
2 Correct 79 ms 85476 KB Output is correct
3 Correct 76 ms 85496 KB Output is correct
4 Correct 80 ms 86208 KB Output is correct
5 Correct 77 ms 86136 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 85496 KB Output is correct
2 Correct 79 ms 85476 KB Output is correct
3 Correct 76 ms 85496 KB Output is correct
4 Correct 80 ms 86208 KB Output is correct
5 Correct 77 ms 86136 KB Output is correct
6 Correct 79 ms 85624 KB Output is correct
7 Correct 80 ms 85528 KB Output is correct
8 Correct 95 ms 85696 KB Output is correct
9 Correct 85 ms 85664 KB Output is correct
10 Correct 84 ms 86188 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 85496 KB Output is correct
2 Correct 79 ms 85476 KB Output is correct
3 Correct 76 ms 85496 KB Output is correct
4 Correct 80 ms 86208 KB Output is correct
5 Correct 77 ms 86136 KB Output is correct
6 Correct 79 ms 85624 KB Output is correct
7 Correct 80 ms 85528 KB Output is correct
8 Correct 95 ms 85696 KB Output is correct
9 Correct 85 ms 85664 KB Output is correct
10 Correct 84 ms 86188 KB Output is correct
11 Correct 350 ms 110788 KB Output is correct
12 Correct 118 ms 106816 KB Output is correct
13 Correct 134 ms 109520 KB Output is correct
14 Correct 596 ms 120256 KB Output is correct
15 Correct 204 ms 110244 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 85496 KB Output is correct
2 Correct 79 ms 85476 KB Output is correct
3 Correct 76 ms 85496 KB Output is correct
4 Correct 80 ms 86208 KB Output is correct
5 Correct 77 ms 86136 KB Output is correct
6 Correct 79 ms 85624 KB Output is correct
7 Correct 80 ms 85528 KB Output is correct
8 Correct 95 ms 85696 KB Output is correct
9 Correct 85 ms 85664 KB Output is correct
10 Correct 84 ms 86188 KB Output is correct
11 Correct 350 ms 110788 KB Output is correct
12 Correct 118 ms 106816 KB Output is correct
13 Correct 134 ms 109520 KB Output is correct
14 Correct 596 ms 120256 KB Output is correct
15 Correct 204 ms 110244 KB Output is correct
16 Runtime error 286 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -