Submission #1122238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122238		Hamed_Ghaffari	Robots (APIO13_robots)	C++17	100 / 100	928 ms	92276 KiB

robots

#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 2e5 + 5;
const int LOG = 23;

int n, h, w;
char a[500][500];
int dp[500][500][9][9];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
pii nxt[500][500][4];
bool vis[500][500][4], mark[500][500];

bool bad(int x, int y) {
    return x<0 || x>=h || y<0 || y>=w || a[x][y]=='x';
}

pii dfs(int x, int y, int d) {
    if(bad(x,y)) return Mp(x-dx[d], y-dy[d]);
    if(vis[x][y][d]) return nxt[x][y][d];
    vis[x][y][d] = 1;
    int d2=d;
    if(a[x][y]=='A') (d2 += 3) %= 4;
    if(a[x][y]=='C') (d2 += 1) %= 4;
    return nxt[x][y][d] = dfs(x+dx[d2], y+dy[d2], d2);
}

void bfs(int l, int r) {
    vector<pair<int, pii>> S;
    for(int x=0; x<h; x++)
        for(int y=0; y<w; y++) {
            for(int m=l; m<r; m++)
                mins(dp[x][y][l][r], dp[x][y][l][m]+dp[x][y][m+1][r]);
            if(dp[x][y][l][r]!=1e9) S.pb(Mp(dp[x][y][l][r], Mp(x,y)));
        }
    sort(S.rbegin(), S.rend());
    queue<pair<int, pii>> q;
    memset(mark, 0, sizeof(mark));
    while(SZ(S)+SZ(q)) {
        pair<int, pii> v;
        if(q.empty() || (SZ(S) && S.back().X<=q.front().X)) {
            v = S.back();
            S.pop_back();
        }
        else {
            v = q.front();
            q.pop();
        }
        if(mark[v.Y.X][v.Y.Y]) continue;
        mark[v.Y.X][v.Y.Y] = 1;
        for(int d=0; d<4; d++) {
            pii u = nxt[v.Y.X][v.Y.Y][d];
            if(!bad(u.X, u.Y) && dp[u.X][u.Y][l][r]>v.X+1)
                q.push(Mp(dp[u.X][u.Y][l][r] = v.X+1, u));
        }
    }
}

void Main() {
    cin >> n >> w >> h;
    for(int i=0; i<h; i++)
        for(int j=0; j<w; j++) {
            cin >> a[i][j];
            for(int l=0; l<n; l++)
                for(int r=l; r<n; r++)
                    dp[i][j][l][r] = 1e9;
            int val = a[i][j]-'0';
            if(1<=val && val<=n) dp[i][j][val-1][val-1]=0;
            for(int d=0; d<4; d++)
                nxt[i][j][d] = Mp(-1, -1);
        }
    for(int i=0; i<h; i++)
        for(int j=0; j<w; j++)
            for(int d=0; d<4; d++)
                if(!vis[i][j][d])
                    dfs(i, j, d);
    for(int ln=1; ln<=n; ln++)
        for(int l=0, r=ln-1; r<n; l++, r++)
            bfs(l, r);
    int ans=1e9;
    for(int i=0; i<h; i++)
        for(int j=0; j<w; j++)
            mins(ans, dp[i][j][0][n-1]);
    cout << (ans==1e9 ? -1 : ans) << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

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