oj.uz

Submission #261476

# Submission time Handle Problem Language Result Execution time Memory
261476 2020-08-11T18:44:49 Z brcode Robots (APIO13_robots) C++14
100 / 100
 1424 ms 144596 KB 
#include <iostream>
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
using namespace std;
const int MAXN = 501;
char grid[MAXN][MAXN];
int dp[MAXN][MAXN][10][10];
vector<pair<int,int>> res[MAXN*MAXN];
pair<int,int> visited[MAXN][MAXN][5];
pair<int,int> bot[10];
int dx[6] = {0,0,1,0,-1};
int dy[6] = {0,1,0,-1,0};
int n,h,w;
bool check(int i,int j){
    if(i<=0||j<=0||i>w||j>h||grid[i][j] == 'x'){
        return false;
    }
    return true;
}
pair<int,int> dfs(int i,int j,int dir){
    if(visited[i][j][dir]!=make_pair(0,0)){
        
        return visited[i][j][dir];
    }
    
    if(grid[i][j]!='x' && grid[i][j]!='C' && grid[i][j]!='A'){
        if(check(i+dx[dir],j+dy[dir])){
            
            return visited[i][j][dir] = dfs(i+dx[dir],j+dy[dir],dir);
        }else{
            
            return make_pair(i,j);
        }
        
    }
    if(grid[i][j]=='A'){
        int newdir = dir;
        newdir--;
        if(newdir == 0){
            newdir = 4;
        }
        if(check( i+dx[newdir],j+dy[newdir])){
            return visited[i][j][dir] = dfs(i+dx[newdir],j+dy[newdir],newdir);
        }else{
            return make_pair(i,j);
        }
        
    }
    
    if(grid[i][j]=='C'){
        int newdir = dir;
        newdir++;
        if(newdir == 5){
            newdir = 1;
        }
        if(check(i+dx[newdir],j+dy[newdir])){
            return visited[i][j][dir] = dfs(i+dx[newdir],j+dy[newdir],newdir);
        }else{
            return make_pair(i,j);
        }
    }
    return make_pair(0,0);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>w>>h;
    swap(w,h);
    int mx = h*w;
    for(int i=1;i<=w;i++){
        for(int j=1;j<=h;j++){
            char x;
            cin>>x;
            grid[i][j] = x;
            
            int y = x-'0';
            if(y>=1 && y<=9){
                bot[y] = make_pair(i,j);
            }
            
            
        }
    }
    for(int i=1;i<=w;i++){
        for(int j=1;j<=h;j++){
            for(int x=1;x<=n;x++){
                for(int y=1;y<=n;y++){
                    dp[i][j][x][y] = 1e9;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        
                dp[bot[i].first][bot[i].second][i][i] = 0;
        //  cout<<i<<" "<<bot[i].first<<" "<<bot[i].second<<endl;
        
    }
    for(int i=1;i<=w;i++){
        for(int j=1;j<=h;j++){
            if(grid[i][j] == 'x'){
                continue;
            }
            if(visited[i][j][1]== make_pair(0,0)){
                dfs(i,j,1);
            }
            if(visited[i][j][2]== make_pair(0,0)){
                dfs(i,j,2);
            }
            if(visited[i][j][3]== make_pair(0,0)){
                dfs(i,j,3);
            }
            if(visited[i][j][4]== make_pair(0,0)){
                dfs(i,j,4);
            }
        }
    }
    //cout<<visited[5][5][1].first<<" "<<visited[5][5][1].second<<endl;
    for(int len=0;len<=n-1;len++){
        for(int x=1;x<=n;x++){
            int y = x+len;
            if(y>n){
                break;
            }
            for(int i=1;i<=w;i++){
                for(int j=1;j<=h;j++){
                    for(int z=x;z<y;z++){
                        if(i==1 && j==1 && x==1 && y==4 && z==2){
                            //cout<<dp[i][j][z+1][y]<<endl;
                        }
                        dp[i][j][x][y] = min(dp[i][j][x][y],dp[i][j][x][z]+dp[i][j][z+1][y]);
                    }
                }
            }
            
            for(int i=0;i<=w*h;i++){
                if(res[i].size()){
                    res[i].clear();
                }
            }
            for(int i=1;i<=w;i++){
                for(int j=1;j<=h;j++){
                    if(dp[i][j][x][y]!=1e9){
                        res[dp[i][j][x][y]].push_back(make_pair(i,j));
                        
                    }
                }
            }
            for(int i=0;i<=w*h;i++){
                for(auto tmp:res[i]){
                    
                    for(int dir=1;dir<=4;dir++){
                        
                        if(visited[tmp.first][tmp.second][dir].first == tmp.first && visited[tmp.first][tmp.second][dir].second == tmp.second){
                            continue;
                        }
                        if(visited[tmp.first][tmp.second][dir].first == 0 && visited[tmp.first][tmp.second][dir].second == 0){
                            continue;
                        }
                        if(dp[visited[tmp.first][tmp.second][dir].first][visited[tmp.first][tmp.second][dir].second][x][y]>i+1){
                            dp[visited[tmp.first][tmp.second][dir].first][visited[tmp.first][tmp.second][dir].second][x][y] = i+1;
                            res[i+1].push_back(make_pair(visited[tmp.first][tmp.second][dir].first,visited[tmp.first][tmp.second][dir].second));
                            
                        }
                    }
                }
            }
           
        }
    }
    //cout<<visited[1][7][3].first<<" "<<visited[1][7][3].second<<endl;
   // cout<<dp[1][7][3][4]<<endl;
    int ans = 1e9;
    for(int i=1;i<=w;i++){
        for(int j=1;j<=h;j++){
            ans = min(ans,dp[i][j][1][n]);
        }
    }
    if(ans == 1e9){
        ans = -1;
    }
    cout<<ans<<'\n';
}

Compilation message

robots.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
robots.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
robots.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")
 
robots.cpp: In function 'int main()':
robots.cpp:72:9: warning: unused variable 'mx' [-Wunused-variable]
     int mx = h*w;
         ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 4 ms 6400 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 4 ms 6400 KB Output is correct
6 Correct 5 ms 6272 KB Output is correct
7 Correct 5 ms 6272 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 5 ms 6272 KB Output is correct
10 Correct 7 ms 6400 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 4 ms 6400 KB Output is correct
6 Correct 5 ms 6272 KB Output is correct
7 Correct 5 ms 6272 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 5 ms 6272 KB Output is correct
10 Correct 7 ms 6400 KB Output is correct
11 Correct 260 ms 49676 KB Output is correct
12 Correct 39 ms 46200 KB Output is correct
13 Correct 132 ms 47736 KB Output is correct
14 Correct 436 ms 54908 KB Output is correct
15 Correct 220 ms 46968 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 4 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 4 ms 6400 KB Output is correct
6 Correct 5 ms 6272 KB Output is correct
7 Correct 5 ms 6272 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 5 ms 6272 KB Output is correct
10 Correct 7 ms 6400 KB Output is correct
11 Correct 260 ms 49676 KB Output is correct
12 Correct 39 ms 46200 KB Output is correct
13 Correct 132 ms 47736 KB Output is correct
14 Correct 436 ms 54908 KB Output is correct
15 Correct 220 ms 46968 KB Output is correct
16 Correct 557 ms 114544 KB Output is correct
17 Correct 1424 ms 144596 KB Output is correct
18 Correct 647 ms 116592 KB Output is correct
19 Correct 557 ms 114740 KB Output is correct
20 Correct 1000 ms 127404 KB Output is correct