oj.uz

Submission #261273

# Submission time Handle Problem Language Result Execution time Memory
261273 2020-08-11T15:44:52 Z brcode Robots (APIO13_robots) C++14
60 / 100
 822 ms 163840 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
int 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] == 0){
        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]==1){
        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]==2){
        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]==3){
        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;
            if(x=='.'){
                grid[i][j] = 1;
                continue;
            }
            if(x=='x'){
                grid[i][j] = 0;
                continue;
            }
            if(x=='A'){
                grid[i][j] = 2;
                continue;
            }
            if(x=='C'){
                grid[i][j] = 3;
                continue;
            }
            grid[i][j] = 1;
            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] == 0){
                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: In function 'int main()':
robots.cpp:75: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 7 ms 6528 KB Output is correct
2 Correct 5 ms 6400 KB Output is correct
3 Correct 5 ms 6400 KB Output is correct
4 Correct 5 ms 6656 KB Output is correct
5 Correct 5 ms 6656 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6528 KB Output is correct
2 Correct 5 ms 6400 KB Output is correct
3 Correct 5 ms 6400 KB Output is correct
4 Correct 5 ms 6656 KB Output is correct
5 Correct 5 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 5 ms 6656 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6528 KB Output is correct
2 Correct 5 ms 6400 KB Output is correct
3 Correct 5 ms 6400 KB Output is correct
4 Correct 5 ms 6656 KB Output is correct
5 Correct 5 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 5 ms 6656 KB Output is correct
11 Correct 381 ms 65784 KB Output is correct
12 Correct 48 ms 62200 KB Output is correct
13 Correct 191 ms 63980 KB Output is correct
14 Correct 612 ms 70884 KB Output is correct
15 Correct 324 ms 62984 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6528 KB Output is correct
2 Correct 5 ms 6400 KB Output is correct
3 Correct 5 ms 6400 KB Output is correct
4 Correct 5 ms 6656 KB Output is correct
5 Correct 5 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 5 ms 6656 KB Output is correct
11 Correct 381 ms 65784 KB Output is correct
12 Correct 48 ms 62200 KB Output is correct
13 Correct 191 ms 63980 KB Output is correct
14 Correct 612 ms 70884 KB Output is correct
15 Correct 324 ms 62984 KB Output is correct
16 Correct 822 ms 160504 KB Output is correct
17 Runtime error 355 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -