oj.uz

Submission #122097

# Submission time Handle Problem Language Result Execution time Memory
122097 2019-06-27T14:36:45 Z jakob_nogler Robots (APIO13_robots) C++14
60 / 100
 576 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 = 305, dir = 4, R = 9, inf = 10e8;
    
pii nxt[N][N][dir];
int cost[R][N][N], dp[R][R][N][N];
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 < n; k++)
                for(int l = 0; l < n; l++)
                    dp[k][l][i][j] = inf;
        }
    
    
    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[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(dp[lo][hi][pos.fi][pos.se] < v) continue;
            for(int i = hi + 1; i < n; i++)
                if(dp[lo][i][pos.fi][pos.se] > dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){
                    dp[lo][i][pos.fi][pos.se] = dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se];
                    q3[dp[lo][i][pos.fi][pos.se]].push({lo, i, pos.fi, pos.se});
                }
            for(int i = lo - 1; i >= 0; i--)
                if(dp[i][hi][pos.fi][pos.se] > dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){
                    dp[i][hi][pos.fi][pos.se] = dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se];
                    q3[dp[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[lo][hi][nn.fi][nn.se] > dp[lo][hi][pos.fi][pos.se] + 1){
                    dp[lo][hi][nn.fi][nn.se] = dp[lo][hi][pos.fi][pos.se] + 1;
                    q3[dp[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[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 64 ms 63144 KB Output is correct
2 Correct 64 ms 62968 KB Output is correct
3 Correct 66 ms 63096 KB Output is correct
4 Correct 67 ms 63108 KB Output is correct
5 Correct 66 ms 63096 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63144 KB Output is correct
2 Correct 64 ms 62968 KB Output is correct
3 Correct 66 ms 63096 KB Output is correct
4 Correct 67 ms 63108 KB Output is correct
5 Correct 66 ms 63096 KB Output is correct
6 Correct 64 ms 63068 KB Output is correct
7 Correct 65 ms 63096 KB Output is correct
8 Correct 70 ms 63080 KB Output is correct
9 Correct 71 ms 62968 KB Output is correct
10 Correct 66 ms 63096 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63144 KB Output is correct
2 Correct 64 ms 62968 KB Output is correct
3 Correct 66 ms 63096 KB Output is correct
4 Correct 67 ms 63108 KB Output is correct
5 Correct 66 ms 63096 KB Output is correct
6 Correct 64 ms 63068 KB Output is correct
7 Correct 65 ms 63096 KB Output is correct
8 Correct 70 ms 63080 KB Output is correct
9 Correct 71 ms 62968 KB Output is correct
10 Correct 66 ms 63096 KB Output is correct
11 Correct 279 ms 98040 KB Output is correct
12 Correct 86 ms 65828 KB Output is correct
13 Correct 97 ms 85472 KB Output is correct
14 Correct 576 ms 107720 KB Output is correct
15 Correct 177 ms 97768 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63144 KB Output is correct
2 Correct 64 ms 62968 KB Output is correct
3 Correct 66 ms 63096 KB Output is correct
4 Correct 67 ms 63108 KB Output is correct
5 Correct 66 ms 63096 KB Output is correct
6 Correct 64 ms 63068 KB Output is correct
7 Correct 65 ms 63096 KB Output is correct
8 Correct 70 ms 63080 KB Output is correct
9 Correct 71 ms 62968 KB Output is correct
10 Correct 66 ms 63096 KB Output is correct
11 Correct 279 ms 98040 KB Output is correct
12 Correct 86 ms 65828 KB Output is correct
13 Correct 97 ms 85472 KB Output is correct
14 Correct 576 ms 107720 KB Output is correct
15 Correct 177 ms 97768 KB Output is correct
16 Runtime error 216 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -