Submission #1180245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180245		Gray	Robots (APIO13_robots)	C++20	10 / 100	0 ms	328 KiB

robots

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

void solve(){
    ll n, w, h; cin >> n >> w >> h;
    vector<vector<ll>> gr(h, vector<ll>(w));
    vector<pair<ll, ll>> pos(n);
    for (ll i=0; i<h; i++){
        for (ll j=0; j<w; j++){
            char x; cin >> x;
            if (x=='A'){
                gr[i][j]=-1;
            }else if (x=='C'){
                gr[i][j]=-2;
            }else if (x=='x'){
                gr[i][j]=-3;
            }else if (x!='.'){
                gr[i][j]=x-'0';
                pos[x-'0'-1]={i, j};
            }
        }
    }
    // U-0, L-1, D-2, R-3

    vector<pair<ll, ll>> mvs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    vector<vector<vector<pair<ll, ll>>>> path(h, vector<vector<pair<ll, ll>>>(w, vector<pair<ll, ll>>(4, {-1, -1})));
    for (ll i=0; i<h; i++){
        for (ll j=0; j<w; j++){
            for (ll dir=0; dir<4; dir++){
                set<pair<ll, ll>> vis;
                pair<ll, ll> cur = {i, j};
                ll cdir = (dir+(gr[i][j]==-1?1:gr[i][j]==-2?-1:0)+4)%4;
                while (cur.ff+mvs[cdir].ff>=0 and cur.ff+mvs[cdir].ff<h and cur.ss+mvs[cdir].ss>=0 and cur.ss+mvs[cdir].ss<w and gr[cur.ff+mvs[cdir].ff][cur.ss+mvs[cdir].ss]!=-3){
                    vis.insert(cur);
                    cur.ff+=mvs[cdir].ff; cur.ss+=mvs[cdir].ss;
                    if (vis.count(cur)){
                        cur = {-2, -2};
                        break;
                    }
                    if (gr[cur.ff][cur.ss]==-2){
                        cdir = (cdir-1+4)%4;
                    }else if (gr[cur.ff][cur.ss]==-1){
                        cdir = (cdir+1)%4;
                    }
                    if (path[cur.ff][cur.ss][cdir].ff!=-1ll and path[cur.ff][cur.ss][cdir].ss!=-1ll){
                        cur = path[cur.ff][cur.ss][cdir];
                    }
                }
                if (cur!=mp(i, j))path[i][j][dir]=cur;
            }
        }
    }
    vector cost(h, vector(w, vector(h, map<ll, ll>())));
    vector calced(h, vector<ll>(w, 0));
    vector<vector<set<pair<ll, ll>>>> reachable(h, vector<set<pair<ll, ll>>>(w));
    auto precalc = [&](ll si, ll sj){
        priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> que;
        que.push({0, {si, sj}});
        while (!que.empty()){
            ll c; pair<ll, ll> cur; tie(c, cur) = que.top(); que.pop();
            if (cost[si][sj][cur.ff].count(cur.ss)) continue;
            cost[si][sj][cur.ff][cur.ss]=c;
            reachable[si][sj].insert(cur);
            for (ll i=0; i<4; i++){
                if (path[cur.ff][cur.ss][i].ff>=0 and !cost[si][sj][path[cur.ff][cur.ss][i].ff].count(path[cur.ff][cur.ss][i].ss)){
                    que.push({c+1, path[cur.ff][cur.ss][i]});
                }
            }
        }
    };
    auto dist = [&](ll si, ll sj, ll ti, ll tj) -> ll{
        if (!calced[si][sj]){
            precalc(si, sj);
        }
        return (cost[si][sj][ti].count(tj)?cost[si][sj][ti][tj]:-1);
    };
    vector dp(n, vector(n, map<ll, map<ll, ll>>()));
    for (ll i=0; i<n; i++){
        dp[i][i][pos[i].ff][pos[i].ss]=0;
    }
    // cout << n << ln;
    // return;
    for (ll len=1; len<n; len++){
        for (ll i=0; i+len<n; i++){
            ll l=i, r=i+len;
            for (ll j=l; j<r; j++){
                ll m = j;
                for (auto &[x1, ys1]:dp[l][m]){
                    for (auto &[y1, c1]:ys1){
                        for (auto &[x2, ys2]:dp[m+1][r]){
                            for (auto &[y2, c2]:ys2){
                                ll cur = c1+c2;
                                if (!calced[x1][y1]) precalc(x1, y1);
                                if (!calced[x2][y2]) precalc(x2, y2);
                                for (auto [mx, my]:reachable[x1][y1]){
                                    if (!reachable[x2][y2].count({mx, my})) continue;
                                    if (!dp[l][r].count(mx) or !dp[l][r][mx].count(my)) dp[l][r][mx][my]=cur+dist(x1, y1, mx, my)+dist(x2, y2, mx, my);
                                    else dp[l][r][mx][my] = min(dp[l][r][mx][my], cur+dist(x1, y1, mx, my)+dist(x2, y2, mx, my));
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    ll ans=INF;
    for (auto &[posx, posys]:dp[0][n-1]){
        for (auto &[posy, c]:posys){
            ans=min(ans, c);
        }
    }
    cout << (ans==INF?-1:ans) << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40