oj.uz

Submission #258326

# Submission time Handle Problem Language Result Execution time Memory
258326 2020-08-05T18:10:24 Z infinitepro Robots (APIO13_robots) C++17
60 / 100
 1500 ms 129308 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<bool> vb;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

int w, h;
char G[500][500];
vector<vvii> vst(500, vvii(500, vii(4, ii(-2, -2))));
vector<vector<vvi>> dp(10, vector<vvi>(10, vvi(500, vi(500, 9999999))));

void cc(int r, int c, int d){
    // d - 0 => up
    // d - 1 => right
    // d - 2 => down
    // d - 3 => left

    if(vst[r][c][d] != ii(-2, -2)) return;
    vst[r][c][d] = ii(-1, -1);

    int d1 = d;
    if(G[r][c] == 'C') d1++;
    else if(G[r][c] == 'A') d1--;
    d1 = (d1+4)%4;

    int r1 = r, c1 = c;
    if(d1 == 0) r1--;
    else if(d1 == 1) c1++;
    else if(d1 == 2) r1++;
    else if(d1 == 3) c1--;

    if(r1 < 0 || r1 >= h || c1 < 0 || c1 >= w || G[r1][c1] == 'x'){
        vst[r][c][d] = ii(r, c);
    }else{
        cc(r1, c1, d1);
        vst[r][c][d] = vst[r1][c1][d1];
    }
    return;
}

struct node{
    int r, c, cst;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin >> n >> w >> h;

    queue<node> cpc[10];
    for(int r = 0; r < h; r++){
        for(int c = 0; c < w; c++){
            cin >> G[r][c];

            int v = G[r][c]-'0';
            if(0 < v && v < 10){
                cpc[v].push({r, c, 0});
                dp[v][v][r][c] = 0;
            }
        }
    }

    for(int r = 0; r < h; r++){
        for(int c = 0; c < w; c++){
            if(G[r][c] == 'x') continue;

            for(int d = 0; d < 4; d++){
                cc(r, c, d);
            }
        }
    }

    for(int x = 1; x <= n; x++){
        while(!cpc[x].empty()){
            auto zx = cpc[x].front(); cpc[x].pop();
            for(int d = 0; d < 4; d++){
                auto ww = vst[zx.r][zx.c][d];
                if(ww == ii(-1, -1)) continue;
                int r = ww.first, c = ww.second;

                if(zx.cst+1 < dp[x][x][r][c]){
                    dp[x][x][r][c] = zx.cst+1;
                    cpc[x].push({r, c, zx.cst+1});
                }
            }
        }
    }

    for(int sz = 1; sz <= n; sz++){
        for(int L = 1; L+sz <= n; L++){
            int R = L+sz;
            
            auto cmp = [](auto n1, auto n2){return n1.cst > n2.cst;};
            priority_queue<node, vector<node>, decltype(cmp)> rpc(cmp);

            for(int r = 0; r < h; r++){
                for(int c = 0; c < w; c++){
                    for(int M = L; M < R; M++){
                        int vvv = dp[L][M][r][c]+dp[M+1][R][r][c];
                        dp[L][R][r][c] = min(dp[L][R][r][c], vvv);
                    }
                    if(dp[L][R][r][c] != 9999999){
                        rpc.push({r, c, dp[L][R][r][c]});
                    }
                }
            }

            while(!rpc.empty()){
                auto zx = rpc.top(); rpc.pop();
                for(int d = 0; d < 4; d++){
                    auto ww = vst[zx.r][zx.c][d];
                    if(ww == ii(-1, -1)) continue;
                    int r = ww.first, c = ww.second;
                    
                    if(zx.cst+1 < dp[L][R][r][c]){
                        dp[L][R][r][c] = zx.cst+1;
                        rpc.push({r, c, zx.cst+1});
                    }
                }
            }

        }
    }

    int ans = INF;
    for(int r = 0; r < h; r++)
        for(int c = 0; c < w; c++)
            ans = min(ans, dp[1][n][r][c]);

    if(ans == 9999999) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 128760 KB Output is correct
2 Correct 75 ms 128760 KB Output is correct
3 Correct 74 ms 128760 KB Output is correct
4 Correct 89 ms 128760 KB Output is correct
5 Correct 89 ms 128760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 128760 KB Output is correct
2 Correct 75 ms 128760 KB Output is correct
3 Correct 74 ms 128760 KB Output is correct
4 Correct 89 ms 128760 KB Output is correct
5 Correct 89 ms 128760 KB Output is correct
6 Correct 87 ms 128760 KB Output is correct
7 Correct 90 ms 128760 KB Output is correct
8 Correct 88 ms 128760 KB Output is correct
9 Correct 128 ms 128760 KB Output is correct
10 Correct 90 ms 128760 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 128760 KB Output is correct
2 Correct 75 ms 128760 KB Output is correct
3 Correct 74 ms 128760 KB Output is correct
4 Correct 89 ms 128760 KB Output is correct
5 Correct 89 ms 128760 KB Output is correct
6 Correct 87 ms 128760 KB Output is correct
7 Correct 90 ms 128760 KB Output is correct
8 Correct 88 ms 128760 KB Output is correct
9 Correct 128 ms 128760 KB Output is correct
10 Correct 90 ms 128760 KB Output is correct
11 Correct 244 ms 128888 KB Output is correct
12 Correct 96 ms 129016 KB Output is correct
13 Correct 113 ms 129028 KB Output is correct
14 Correct 703 ms 129016 KB Output is correct
15 Correct 182 ms 129016 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 128760 KB Output is correct
2 Correct 75 ms 128760 KB Output is correct
3 Correct 74 ms 128760 KB Output is correct
4 Correct 89 ms 128760 KB Output is correct
5 Correct 89 ms 128760 KB Output is correct
6 Correct 87 ms 128760 KB Output is correct
7 Correct 90 ms 128760 KB Output is correct
8 Correct 88 ms 128760 KB Output is correct
9 Correct 128 ms 128760 KB Output is correct
10 Correct 90 ms 128760 KB Output is correct
11 Correct 244 ms 128888 KB Output is correct
12 Correct 96 ms 129016 KB Output is correct
13 Correct 113 ms 129028 KB Output is correct
14 Correct 703 ms 129016 KB Output is correct
15 Correct 182 ms 129016 KB Output is correct
16 Correct 215 ms 129308 KB Output is correct
17 Execution timed out 1608 ms 129144 KB Time limit exceeded
18 Halted 0 ms 0 KB -