oj.uz

Submission #261473

# Submission time Handle Problem Language Result Execution time Memory
261473 2020-08-11T18:37:53 Z brcode Robots (APIO13_robots) C++14
60 / 100
 644 ms 163844 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 = 510;
char grid[MAXN][MAXN];
int dp[MAXN][MAXN][12][12];
vector<pair<int,int>> res[MAXN*MAXN + 2];
int n,h,w;
int dx[6] = {0,0,1,0,-1};
int dy[6] = {0,1,0,-1,0};
pair<int,int> visited[MAXN][MAXN][5];
pair<int,int> bot[20];
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'){
        int nexti = i+dx[dir];
        int nextj = j+dy[dir];
        
        if(check(nexti,nextj)){
            
            return visited[i][j][dir] = dfs(nexti,nextj,dir);
        }else{
            
            return make_pair(i,j);
        }
        
    }
    if(grid[i][j]=='A'){
        int newdir = dir;
        newdir--;
        if(newdir == 0){
            newdir = 4;
        }
        int nexti = i+dx[newdir];
        int nextj = j+dy[newdir];
        if(check(nexti,nextj)){
            return visited[i][j][dir] = dfs(nexti,nextj,newdir);
        }else{
            return make_pair(i,j);
        }
        
    }
    
    if(grid[i][j]=='C'){
        int newdir = dir;
        newdir++;
        if(newdir == 5){
            newdir = 1;
        }
        int nexti = i+dx[newdir];
        int nextj = j+dy[newdir];
        if(check(nexti,nextj)){
            return visited[i][j][dir] = dfs(nexti,nextj,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';
            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]){
                    int a = tmp.first;
                    int b = tmp.second;
                    for(int dir=1;dir<=4;dir++){
                        int nxti = visited[a][b][dir].first;
                        int nxtj = visited[a][b][dir].second;
                        if(nxti == a && nxtj == b){
                            continue;
                        }
                        if(nxti == 0 && nxtj == 0){
                            continue;
                        }
                        if(dp[nxti][nxtj][x][y]>i+1){
                            dp[nxti][nxtj][x][y] = i+1;
                            res[i+1].push_back(make_pair(nxti,nxtj));
                            
                        }
                    }
                }
            }
           
        }
    }
    //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:79: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 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 6 ms 6656 KB Output is correct
5 Correct 6 ms 6656 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 6 ms 6656 KB Output is correct
5 Correct 6 ms 6656 KB Output is correct
6 Correct 5 ms 6528 KB Output is correct
7 Correct 5 ms 6400 KB Output is correct
8 Correct 5 ms 6528 KB Output is correct
9 Correct 6 ms 6528 KB Output is correct
10 Correct 6 ms 6656 KB Output is correct
11 Correct 303 ms 65144 KB Output is correct
12 Correct 51 ms 61688 KB Output is correct
13 Correct 156 ms 63224 KB Output is correct
14 Correct 500 ms 70264 KB Output is correct
15 Correct 268 ms 62516 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct
3 Correct 5 ms 6528 KB Output is correct
4 Correct 6 ms 6656 KB Output is correct
5 Correct 6 ms 6656 KB Output is correct
6 Correct 5 ms 6528 KB Output is correct
7 Correct 5 ms 6400 KB Output is correct
8 Correct 5 ms 6528 KB Output is correct
9 Correct 6 ms 6528 KB Output is correct
10 Correct 6 ms 6656 KB Output is correct
11 Correct 303 ms 65144 KB Output is correct
12 Correct 51 ms 61688 KB Output is correct
13 Correct 156 ms 63224 KB Output is correct
14 Correct 500 ms 70264 KB Output is correct
15 Correct 268 ms 62516 KB Output is correct
16 Correct 644 ms 159628 KB Output is correct
17 Runtime error 340 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -