oj.uz

Submission #1012844

# Submission time Handle Problem Language Result Execution time Memory
1012844 2024-07-02T17:00:19 Z ttamx Robots (APIO13_robots) C++17
100 / 100
 865 ms 55452 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=10;
const int H=500;
const int INF=1e9;

int n,h,w;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
string a[H];
pair<int,int> pos[H][H][4];
bool vis[H][H][4];
int dp[N][N][H][H];

pair<int,int> dfs(int i,int j,int d){
    if(i<0||i>=h||j<0||j>=w||a[i][j]=='x')return {-1,-1};
    if(vis[i][j][d])return pos[i][j][d];
    vis[i][j][d]=true;
    int nd=d;
    if(a[i][j]=='C')nd=(nd+1)%4;
    if(a[i][j]=='A')nd=(nd+3)%4;
    pos[i][j][d]=dfs(i+dx[nd],j+dy[nd],nd);
    if(pos[i][j][d]==make_pair(-1,-1))pos[i][j][d]={i,j};
    return pos[i][j][d];
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> w >> h;
    for(int i=0;i<h;i++)cin >> a[i];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            for(int d=0;d<4;d++){
                dfs(i,j,d);
            }
        }
    }
    for(int l=0;l<n;l++){
        for(int r=l;r<n;r++){
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    dp[l][r][i][j]=INF;
                }
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(isdigit(a[i][j])){
                int x=a[i][j]-'1';
                auto &dp2=dp[x][x];
                dp2[i][j]=0;
                queue<pair<int,int>> q;
                q.emplace(i,j);
                while(!q.empty()){
                    auto [i,j]=q.front();
                    q.pop();
                    for(int d=0;d<4;d++){
                        pair<int,int> p=pos[i][j][d];
                        if(dp2[p.first][p.second]>dp2[i][j]+1){
                            dp2[p.first][p.second]=dp2[i][j]+1;
                            q.emplace(p);
                        }
                    }
                }
            }
        }
    }
    for(int s=1;s<n;s++){
        for(int l=0,r=s;r<n;l++,r++){
            auto &dp2=dp[l][r];
            for(int m=l;m<r;m++){
                for(int i=0;i<h;i++){
                    for(int j=0;j<w;j++){
                        dp2[i][j]=min(dp2[i][j],dp[l][m][i][j]+dp[m+1][r][i][j]);
                    }
                }
            }
            using T = tuple<int,int,int>;
            priority_queue<T,vector<T>,greater<T>> pq;
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(dp2[i][j]<INF){
                        pq.emplace(dp2[i][j],i,j);
                    }
                }
            }
            while(!pq.empty()){
                auto [d,i,j]=pq.top();
                pq.pop();
                if(d>dp2[i][j])continue;
                for(int k=0;k<4;k++){
                    auto [x,y]=pos[i][j][k];
                    if(dp2[x][y]>d+1){
                        dp2[x][y]=d+1;
                        pq.emplace(d+1,x,y);
                    }
                }
            }
        }
    }
    int ans=INF;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            ans=min(ans,dp[0][n-1][i][j]);
        }
    }
    cout << (ans==INF?-1:ans);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 77 ms 31484 KB Output is correct
12 Correct 5 ms 4956 KB Output is correct
13 Correct 17 ms 21808 KB Output is correct
14 Correct 319 ms 32168 KB Output is correct
15 Correct 55 ms 31496 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 77 ms 31484 KB Output is correct
12 Correct 5 ms 4956 KB Output is correct
13 Correct 17 ms 21808 KB Output is correct
14 Correct 319 ms 32168 KB Output is correct
15 Correct 55 ms 31496 KB Output is correct
16 Correct 83 ms 53812 KB Output is correct
17 Correct 865 ms 55452 KB Output is correct
18 Correct 98 ms 53680 KB Output is correct
19 Correct 58 ms 53788 KB Output is correct
20 Correct 426 ms 54764 KB Output is correct