oj.uz

Submission #233995

# Submission time Handle Problem Language Result Execution time Memory
233995 2020-05-22T17:01:05 Z AQT Robots (APIO13_robots) C++14
60 / 100
 1500 ms 72560 KB 
// Problem : APIO '13 P1 - Robots
// Contest : DMOJ
// URL : https://dmoj.ca/problem/apio13p1
// Memory Limit : 128 MB
// Time Limit : 750 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
 
#include <bits/stdc++.h>
 
using namespace std;
 
int K, N, M;
int dist[10][10][505][505];
vector<pair<int, int>> graph[505][505];
char mp[505][505];
pair<int, int> moves[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
pair<int, int> endpos[4][505][505];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
int oo = INT_MAX>>2;
 
pair<int, int> fnd(int d, int x, int y){
	if(endpos[d][x][y].first){
		return endpos[d][x][y];
	}
	int r = 0;
	if(mp[x][y] == 'A'){
		r = 3;
	}
	if(mp[x][y] == 'C'){
		r = 1;
	}
	if(mp[x+moves[(d+r)%4].first][y+moves[(d+r)%4].second] == 'x'){
		return endpos[d][x][y] = {x, y};
	}
	return endpos[d][x][y] = fnd((d+r)%4, x+moves[(d+r)%4].first, y+moves[(d+r)%4].second);
}
 
int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> K >> M >> N;
	oo = K*M*N;
	for(int l = 1; l<=K; l++){
		for(int r = l; r<=K; r++){
			for(int i = 1; i<=N; i++){
				for(int j = 1; j<=M; j++){
					dist[l][r][i][j] = oo;
				}
			}		
		}
	}
	for(int i = 1; i<=N; i++){
		for(int j = 1; j<=M; j++){
			cin >> mp[i][j];
			if(mp[i][j] > '0' && mp[i][j] <= '9'){
				dist[mp[i][j]-'0'][mp[i][j]-'0'][i][j] = 0;
			}
		}
	}
	for(int i = 0; i<=N+1; i++){
		mp[i][0] = mp[i][M+1] = 'x';
	}
	for(int j = 0; j<=M+1; j++){
		mp[0][j] = mp[N+1][j] = 'x';
	}
	for(int i = 1; i<=N; i++){
		for(int j = 1; j<=M; j++){
			for(int k = 0; k<4; k++){
				graph[i][j].push_back(fnd(k, i, j));
			}
		}
	}
	for(int len = 1; len<=K; len++){
		for(int l = 1; l+len-1<=K; l++){
			int r = l+len-1;
			for(int i = 1; i<=N; i++){
				for(int j = 1; j<=M; j++){
					for(int k = l; k<r; k++){
						dist[l][r][i][j] = min(dist[l][k][i][j] + dist[k+1][r][i][j], dist[l][r][i][j]);
					}
					if(dist[l][r][i][j] != oo){
						pq.push({dist[l][r][i][j], {i, j}});
					}
				}
			}
			while(pq.size()){
				auto p = pq.top();
				pq.pop();
				if(dist[l][r][p.second.first][p.second.second] != p.first){
					continue;
				}
				for(auto e : graph[p.second.first][p.second.second]){
					if(dist[l][r][e.first][e.second] > dist[l][r][p.second.first][p.second.second] + 1){
						dist[l][r][e.first][e.second] = dist[l][r][p.second.first][p.second.second] + 1;
						pq.push({dist[l][r][e.first][e.second], {e.first, e.second}});
					}
				}
			}
		}
	}
	int ans = oo;
	for(int i = 1; i<=N; i++){
		for(int j = 1; j<=M; j++){
			ans = min(dist[1][K][i][j], ans);
		}
	}
	/*
	for(int l = 1; l<=K; l++){
		for(int r = l; r<=K; r++){
			cout << l << " " << r << "\n";
			for(int i = 1; i<=N; i++){
				for(int j = 1; j<=M; j++){
					if(dist[l][r][i][j] == INT_MAX>>2){
						cout << 'X';
					}
					else{
						cout << dist[l][r][i][j];
					}
				}
				cout << "\n";
			}
			cout << "\n";
		}
	}
	*/
	cout << (ans == oo ? -1 : ans);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6400 KB Output is correct
2 Correct 8 ms 6400 KB Output is correct
3 Correct 8 ms 6400 KB Output is correct
4 Correct 8 ms 6528 KB Output is correct
5 Correct 8 ms 6528 KB Output is correct
6 Correct 8 ms 6400 KB Output is correct
7 Correct 9 ms 6400 KB Output is correct
8 Correct 8 ms 6400 KB Output is correct
9 Correct 8 ms 6400 KB Output is correct
10 Correct 9 ms 6656 KB Output is correct
11 Correct 177 ms 42680 KB Output is correct
12 Correct 35 ms 16000 KB Output is correct
13 Correct 56 ms 32384 KB Output is correct
14 Correct 663 ms 42996 KB Output is correct
15 Correct 113 ms 42360 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6400 KB Output is correct
2 Correct 8 ms 6400 KB Output is correct
3 Correct 8 ms 6400 KB Output is correct
4 Correct 8 ms 6528 KB Output is correct
5 Correct 8 ms 6528 KB Output is correct
6 Correct 8 ms 6400 KB Output is correct
7 Correct 9 ms 6400 KB Output is correct
8 Correct 8 ms 6400 KB Output is correct
9 Correct 8 ms 6400 KB Output is correct
10 Correct 9 ms 6656 KB Output is correct
11 Correct 177 ms 42680 KB Output is correct
12 Correct 35 ms 16000 KB Output is correct
13 Correct 56 ms 32384 KB Output is correct
14 Correct 663 ms 42996 KB Output is correct
15 Correct 113 ms 42360 KB Output is correct
16 Correct 154 ms 70908 KB Output is correct
17 Execution timed out 1596 ms 72560 KB Time limit exceeded
18 Halted 0 ms 0 KB -