oj.uz

Submission #258568

# Submission time Handle Problem Language Result Execution time Memory
258568 2020-08-06T07:12:24 Z pure_mem Robots (APIO13_robots) C++14
100 / 100
 429 ms 125560 KB 
#include <bits/stdc++.h>
 
#define ll long long
#define X first
#define Y second
#define MP make_pair
 
using namespace std;
 
const int inf = 250000, N = 500;
 
char a[N][N];
int n, w, h, dp[9][9][N][N];
pair<int, int> end_pos[4][N][N];
vector< pair<int, int> > q[inf];
vector< pair< int, pair< int, int > > > temp;
 
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	memset(dp, 0x3f, sizeof(dp));
 
    cin >> n >> w >> h;

    for(int i = 0;i < h;i++){
    	for(int j = 0;j < w;j++){
    		cin >> a[i][j];
    		if(a[i][j] >= '0' && a[i][j] <= '9'){
    			dp[a[i][j] - '0' - 1][a[i][j] - '0' - 1][i][j] = 0;	
    		}
    	}
    }
    for(int x = 0;x < h;x++){
    	for(int y = 0;y < w;y++){
    		if(a[x][y] == 'x')
    			continue;
    		for(int d = 0;d < 4;d++){
    			int dr = d;
    			if(a[x][y] == 'A')
    				dr = (dr + 3) % 4;
    			else if(a[x][y] == 'C')
    				dr = (dr + 1) % 4;
    			pair<int, int> pos = MP(x, y);
    			while(true){
    				if(dr == 0){
    					if(pos.X - 1 >= 0 && pos.X - 1 < h && pos.Y >= 0 && pos.Y < w && a[pos.X - 1][pos.Y] != 'x')
    						pos.X -= 1;
    					else
    						break;
    				}
    				else if(dr == 3){
    					if(pos.X >= 0 && pos.X < h && pos.Y - 1 >= 0 && pos.Y - 1 < w && a[pos.X][pos.Y - 1] != 'x')
    						pos.Y -= 1;
    					else
    						break;
    				}	
    				else if(dr == 2){
    					if(pos.X + 1 >= 0 && pos.X + 1 < h && pos.Y >= 0 && pos.Y < w && a[pos.X + 1][pos.Y] != 'x')
    						pos.X += 1;
    					else
    						break;
    				}             
    				else if(dr == 1){
    					if(pos.X >= 0 && pos.X < h && pos.Y + 1 >= 0 && pos.Y + 1 < w && a[pos.X][pos.Y + 1] != 'x')
    						pos.Y += 1;
    					else
    						break;
    				}
    				if(end_pos[dr][pos.X][pos.Y] != MP(0, 0)){
    					pos = end_pos[dr][pos.X][pos.Y];
    					break;
    				}
    				else{
    					temp.push_back(MP(dr, pos));
    				} 
    				if(a[pos.X][pos.Y] == 'A')
    					dr = (dr + 3) % 4;
    				else if(a[pos.X][pos.Y] == 'C')
    					dr = (dr + 1) % 4;
    			}
    			end_pos[d][x][y] = pos;
    			while(!temp.empty()){
    				end_pos[temp.back().X][temp.back().Y.X][temp.back().Y.Y] = pos;
    				temp.pop_back();
    			}
    		}
    	}
    }

    int ans = inf;
    for(int len = 1;len < n;len++){
    	for(int A = 0;A + len - 1 < n;A++){
    		int B = A + len - 1;
    		for(int x = 0;x < h;x++){
   			 	for(int y = 0;y < w;y++){
                	if(a[x][y] != 'x' && dp[A][B][x][y] < inf){
                		q[dp[A][B][x][y]].push_back(MP(x, y));
                	}
    			}
    		}
    		for(int it = 0;it < inf;it++){
    			for(pair<int, int> pos: q[it]){
    				for(int dr = 0;dr < 4;dr++){
    					pair<int, int> to = end_pos[dr][pos.X][pos.Y];
    					if(dp[A][B][pos.X][pos.Y] + 1 < dp[A][B][to.X][to.Y]){
    						dp[A][B][to.X][to.Y] = dp[A][B][pos.X][pos.Y] + 1;	
    						if(it + 1 < inf)
    							q[it + 1].push_back(to);
    					}		
    				}
    		   }
    		   q[it].clear();
    		}
    	}
    	for(int A = 0;A + len < n;A++){
    		int B = A + len;
    		for(int x = 0;x < h;x++){
   			 	for(int y = 0;y < w;y++){
                	if(a[x][y] != 'x'){
                		for(int C = A;C < B;C++){
                			dp[A][B][x][y] = min(dp[A][B][x][y], dp[A][C][x][y] + dp[C + 1][B][x][y]);
                		}
                	}
    			}
    		}
    	}
    }
                                          /*
    cerr << end_pos[0][3][0].X << " " << end_pos[0][3][0].Y << "\n"; 
    cerr << dp[1][1][1][0] << "\n";         */

    for(int x = 0;x < h;x++){
    	for(int y = 0;y < w;y++){
    		if(a[x][y] != 'x')
    			ans = min(ans, dp[0][n - 1][x][y]);
    	}
    }
	                                            
	if(ans >= inf)
		ans = -1;
	cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 85500 KB Output is correct
2 Correct 42 ms 85476 KB Output is correct
3 Correct 43 ms 85496 KB Output is correct
4 Correct 42 ms 85624 KB Output is correct
5 Correct 43 ms 85624 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 85500 KB Output is correct
2 Correct 42 ms 85476 KB Output is correct
3 Correct 43 ms 85496 KB Output is correct
4 Correct 42 ms 85624 KB Output is correct
5 Correct 43 ms 85624 KB Output is correct
6 Correct 43 ms 85496 KB Output is correct
7 Correct 44 ms 85624 KB Output is correct
8 Correct 42 ms 85496 KB Output is correct
9 Correct 43 ms 85632 KB Output is correct
10 Correct 42 ms 85624 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 85500 KB Output is correct
2 Correct 42 ms 85476 KB Output is correct
3 Correct 43 ms 85496 KB Output is correct
4 Correct 42 ms 85624 KB Output is correct
5 Correct 43 ms 85624 KB Output is correct
6 Correct 43 ms 85496 KB Output is correct
7 Correct 44 ms 85624 KB Output is correct
8 Correct 42 ms 85496 KB Output is correct
9 Correct 43 ms 85632 KB Output is correct
10 Correct 42 ms 85624 KB Output is correct
11 Correct 113 ms 94200 KB Output is correct
12 Correct 48 ms 90232 KB Output is correct
13 Correct 70 ms 90360 KB Output is correct
14 Correct 196 ms 99448 KB Output is correct
15 Correct 96 ms 91640 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 85500 KB Output is correct
2 Correct 42 ms 85476 KB Output is correct
3 Correct 43 ms 85496 KB Output is correct
4 Correct 42 ms 85624 KB Output is correct
5 Correct 43 ms 85624 KB Output is correct
6 Correct 43 ms 85496 KB Output is correct
7 Correct 44 ms 85624 KB Output is correct
8 Correct 42 ms 85496 KB Output is correct
9 Correct 43 ms 85632 KB Output is correct
10 Correct 42 ms 85624 KB Output is correct
11 Correct 113 ms 94200 KB Output is correct
12 Correct 48 ms 90232 KB Output is correct
13 Correct 70 ms 90360 KB Output is correct
14 Correct 196 ms 99448 KB Output is correct
15 Correct 96 ms 91640 KB Output is correct
16 Correct 145 ms 93912 KB Output is correct
17 Correct 429 ms 125560 KB Output is correct
18 Correct 153 ms 97904 KB Output is correct
19 Correct 116 ms 93816 KB Output is correct
20 Correct 264 ms 108432 KB Output is correct