oj.uz

Submission #258367

# Submission time Handle Problem Language Result Execution time Memory
258367 2020-08-05T20:40:12 Z infinitepro Robots (APIO13_robots) C++17
100 / 100
 856 ms 129436 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
#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;};
            vector<node> rpc;

            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_back({r, c, dp[L][R][r][c]});
                    }
                }
            }

            sort(all(rpc), cmp);
            queue<node> rpc1;
        
            while(!rpc.empty() || !rpc1.empty()){
                node zx;

                if(rpc.empty()){
                    zx = rpc1.front(); rpc1.pop();                    
                }else if(rpc1.empty()){
                    zx = rpc.back(); rpc.pop_back();
                }else if(rpc.back().cst <= rpc1.front().cst){
                    zx = rpc.back(); rpc.pop_back();
                }else{
                    zx = rpc1.front(); rpc1.pop();                    
                }

                for(int d = 0; d < 4; d++){
                    auto ww = vst[zx.r][zx.c][d];
                    if(ww == ii(-1, -1) or ww == ii(-2, -2)) 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;
                        rpc1.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;
}

Compilation message

robots.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
robots.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
robots.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 128740 KB Output is correct
2 Correct 91 ms 128888 KB Output is correct
3 Correct 77 ms 128760 KB Output is correct
4 Correct 98 ms 128760 KB Output is correct
5 Correct 79 ms 128760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 128740 KB Output is correct
2 Correct 91 ms 128888 KB Output is correct
3 Correct 77 ms 128760 KB Output is correct
4 Correct 98 ms 128760 KB Output is correct
5 Correct 79 ms 128760 KB Output is correct
6 Correct 92 ms 128772 KB Output is correct
7 Correct 82 ms 128760 KB Output is correct
8 Correct 81 ms 128760 KB Output is correct
9 Correct 82 ms 128760 KB Output is correct
10 Correct 78 ms 128852 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 128740 KB Output is correct
2 Correct 91 ms 128888 KB Output is correct
3 Correct 77 ms 128760 KB Output is correct
4 Correct 98 ms 128760 KB Output is correct
5 Correct 79 ms 128760 KB Output is correct
6 Correct 92 ms 128772 KB Output is correct
7 Correct 82 ms 128760 KB Output is correct
8 Correct 81 ms 128760 KB Output is correct
9 Correct 82 ms 128760 KB Output is correct
10 Correct 78 ms 128852 KB Output is correct
11 Correct 173 ms 129016 KB Output is correct
12 Correct 96 ms 128892 KB Output is correct
13 Correct 111 ms 129016 KB Output is correct
14 Correct 367 ms 129016 KB Output is correct
15 Correct 151 ms 128888 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 128740 KB Output is correct
2 Correct 91 ms 128888 KB Output is correct
3 Correct 77 ms 128760 KB Output is correct
4 Correct 98 ms 128760 KB Output is correct
5 Correct 79 ms 128760 KB Output is correct
6 Correct 92 ms 128772 KB Output is correct
7 Correct 82 ms 128760 KB Output is correct
8 Correct 81 ms 128760 KB Output is correct
9 Correct 82 ms 128760 KB Output is correct
10 Correct 78 ms 128852 KB Output is correct
11 Correct 173 ms 129016 KB Output is correct
12 Correct 96 ms 128892 KB Output is correct
13 Correct 111 ms 129016 KB Output is correct
14 Correct 367 ms 129016 KB Output is correct
15 Correct 151 ms 128888 KB Output is correct
16 Correct 216 ms 129436 KB Output is correct
17 Correct 856 ms 129272 KB Output is correct
18 Correct 249 ms 129272 KB Output is correct
19 Correct 207 ms 129272 KB Output is correct
20 Correct 540 ms 129400 KB Output is correct