Submission #1180517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180517		Gray	Robots (APIO13_robots)	C++20	30 / 100	432 ms	74100 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};
            }
        }
    }
    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})));
    set<pair<ll, ll>> vis;
    for (ll i=0; i<h; i++){
        for (ll j=0; j<w; j++){
            for (ll dir=0; dir<4; dir++){
                vis.clear();
                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 (path[cur.ff][cur.ss][cdir].ff!=-1){
                        cur = path[cur.ff][cur.ss][cdir];
                        break;
                    }
                    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 (cur!=mp(i, j)) path[i][j][dir]=cur;
            }
        }
    }
    vector dp(n, vector(n, vector(h, vector(w, INF))));
    priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> que;
    for (ll i=0; i<n; i++){
        que.push({0, pos[i]});
        while (!que.empty()){
            ll c; pair<ll, ll> cord; tie(c, cord)=que.top(); que.pop();
            if (dp[i][i][cord.ff][cord.ss]<=c) continue;
            dp[i][i][cord.ff][cord.ss]=c;
            for (ll j=0; j<4; j++){
                if (path[cord.ff][cord.ss][j].ff>=0 and dp[i][i][path[cord.ff][cord.ss][j].ff][path[cord.ff][cord.ss][j].ss]==INF){
                    que.push({c+1, path[cord.ff][cord.ss][j]});
                }
            }
        }
    }
    // for (ll i=0; i<h; i++){
    //     for (ll j=0; j<w; j++){
    //         cout << dp[1][1][i][j] << " ";
    //     }
    //     cout << ln;
    // }
    for (ll len=1; len<n; len++){
        for (ll i=0; i+len<n; i++){
            ll l=i, r=i+len;
            for (ll m=l; m<r; m++){
                for (ll x=0; x<h; x++){
                    for (ll y=0; y<w; y++){
                        dp[l][r][x][y]=min(dp[l][r][x][y], dp[l][m][x][y]+dp[m+1][r][x][y]);
                    }
                }
            }
            for (ll x=0; x<h; x++){
                for (ll y=0; y<w; y++){
                    que.push({dp[l][r][x][y], {x, y}});
                }
            }
            dp[l][r].assign(h, vector<ll>(w, INF));
            while (!que.empty()){
                ll c; pair<ll, ll> cord; tie(c, cord)=que.top(); que.pop();
                if (dp[l][r][cord.ff][cord.ss]<=c) continue;
                dp[l][r][cord.ff][cord.ss]=c;
                for (ll j=0; j<4; j++){
                    if (path[cord.ff][cord.ss][j].ff>=0 and dp[i][i][path[cord.ff][cord.ss][j].ff][path[cord.ff][cord.ss][j].ss]==INF){
                        que.push({c+1, path[cord.ff][cord.ss][j]});
                    }
                }
            }
        }
    }
    ll res=INF;
    for (ll i=0; i<h; i++){
        for (ll j=0; j<w; j++){
            res=min(res, dp[0][n-1][i][j]);
        }
    }
    cout << (res==INF?-1:res) << 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: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40