Submission #1168771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168771		byunjaewoo	Robots (APIO13_robots)	C++20	60 / 100	1580 ms	70276 KiB

robots

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

const int N=10, X=510, INF=1e9;
int n, h, w, ans=INF, x[N], y[N], a[X][X], nxt[X][X], dp[N][N][X][X];
int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
vector<pair<int, int>> adj[X][X];
queue<pair<int, pair<int, int>>> que;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>w>>h;
    for(int i=1; i<=h; i++) {
        string s; cin>>s;
        for(int j=1; j<=w; j++) {
            if('1'<=s[j-1] && s[j-1]<='9') x[s[j-1]-'0']=i, y[s[j-1]-'0']=j;
            else if(s[j-1]=='A') a[i][j]=1;
            else if(s[j-1]=='C') a[i][j]=2;
            else if(s[j-1]=='x') a[i][j]=-1;
        }
    }
    for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) {
        for(int d=0; d<4; d++) {
            int ii=i, jj=j, dd=d;
            while(true) {
                if(ii+dx[dd]<1 || ii+dx[dd]>h || jj+dy[dd]<1 || jj+dy[dd]>w || a[ii+dx[dd]][jj+dy[dd]]<0) break;
                ii+=dx[dd], jj+=dy[dd];
                if(a[ii][jj]==1) dd=(dd+3)%4;
                if(a[ii][jj]==2) dd=(dd+1)%4;
            }
            if(i!=ii || j!=jj) adj[i][j].push_back({ii, jj});
        }
    }
    for(int l=1; l<=n; l++) for(int r=l; r<=n; r++) for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) dp[l][r][i][j]=INF;
    for(int i=1; i<=n; i++) dp[i][i][x[i]][y[i]]=0;
    for(int d=1; d<=n; d++) {
        for(int l=1; l<=n-d+1; l++) {
            int r=l+d-1;
            for(int k=l; k<r; k++) for(int i=1; i<=h; i++) for(int j=1; j<=w; j++)
                dp[l][r][i][j]=min(dp[l][r][i][j], dp[l][k][i][j]+dp[k+1][r][i][j]);
            vector<pair<int, pair<int, int>>> vec;
            for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) vec.push_back({dp[l][r][i][j], {i, j}});
            sort(vec.rbegin(), vec.rend());
            while(!vec.empty() || !que.empty()) {
                int d=0, x=0, y=0;
                if(vec.empty() || !que.empty() && que.front().first<vec.back().first)
                    d=que.front().first, x=que.front().second.first, y=que.front().second.second, que.pop();
                else d=vec.back().first, x=vec.back().second.first, y=vec.back().second.second, vec.pop_back();
                for(auto [i, j]:adj[x][y]) if(dp[l][r][i][j]>d+1)
                    dp[l][r][i][j]=d+1, que.push({d+1, {i, j}});
            }
        }
    }
    for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) ans=min(ans, dp[1][n][i][j]);
    if(ans>=INF/10) ans=-1;
    cout<<ans;
    return 0;
}

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