oj.uz

Submission #258057

# Submission time Handle Problem Language Result Execution time Memory
258057 2020-08-05T09:31:08 Z infinitepro Robots (APIO13_robots) C++17
60 / 100
 1500 ms 125432 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<vvi> vst(500, vvi(500, vi(4, -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] != -2) return;
    vst[r][c][d] = -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] = r*w+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++){
            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++){
                int ww = vst[zx.r][zx.c][d];
                if(ww < 0) continue;
                int c = ww%w, r = (ww-c)/w;
                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++){
                    int ww = vst[zx.r][zx.c][d];
                    if(ww < 0) continue;
                    int c = ww%w, r = (ww-c)/w;
                    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 86 ms 124792 KB Output is correct
2 Correct 73 ms 124824 KB Output is correct
3 Correct 72 ms 124740 KB Output is correct
4 Correct 87 ms 124920 KB Output is correct
5 Correct 89 ms 124792 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 124792 KB Output is correct
2 Correct 73 ms 124824 KB Output is correct
3 Correct 72 ms 124740 KB Output is correct
4 Correct 87 ms 124920 KB Output is correct
5 Correct 89 ms 124792 KB Output is correct
6 Correct 75 ms 124792 KB Output is correct
7 Correct 73 ms 124800 KB Output is correct
8 Correct 77 ms 124920 KB Output is correct
9 Correct 74 ms 124792 KB Output is correct
10 Correct 77 ms 124792 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 124792 KB Output is correct
2 Correct 73 ms 124824 KB Output is correct
3 Correct 72 ms 124740 KB Output is correct
4 Correct 87 ms 124920 KB Output is correct
5 Correct 89 ms 124792 KB Output is correct
6 Correct 75 ms 124792 KB Output is correct
7 Correct 73 ms 124800 KB Output is correct
8 Correct 77 ms 124920 KB Output is correct
9 Correct 74 ms 124792 KB Output is correct
10 Correct 77 ms 124792 KB Output is correct
11 Correct 274 ms 125176 KB Output is correct
12 Correct 94 ms 125048 KB Output is correct
13 Correct 107 ms 125228 KB Output is correct
14 Correct 809 ms 125092 KB Output is correct
15 Correct 183 ms 125180 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 124792 KB Output is correct
2 Correct 73 ms 124824 KB Output is correct
3 Correct 72 ms 124740 KB Output is correct
4 Correct 87 ms 124920 KB Output is correct
5 Correct 89 ms 124792 KB Output is correct
6 Correct 75 ms 124792 KB Output is correct
7 Correct 73 ms 124800 KB Output is correct
8 Correct 77 ms 124920 KB Output is correct
9 Correct 74 ms 124792 KB Output is correct
10 Correct 77 ms 124792 KB Output is correct
11 Correct 274 ms 125176 KB Output is correct
12 Correct 94 ms 125048 KB Output is correct
13 Correct 107 ms 125228 KB Output is correct
14 Correct 809 ms 125092 KB Output is correct
15 Correct 183 ms 125180 KB Output is correct
16 Correct 209 ms 125432 KB Output is correct
17 Execution timed out 1599 ms 125304 KB Time limit exceeded
18 Halted 0 ms 0 KB -