oj.uz

Submission #233989

# Submission time Handle Problem Language Result Execution time Memory
233989 2020-05-22T16:47:00 Z AQT Robots (APIO13_robots) C++14
60 / 100
 1500 ms 72816 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;
const 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;
	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 8 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 8 ms 6528 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 8 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 8 ms 6528 KB Output is correct
11 Correct 164 ms 42552 KB Output is correct
12 Correct 35 ms 16000 KB Output is correct
13 Correct 55 ms 32376 KB Output is correct
14 Correct 652 ms 43124 KB Output is correct
15 Correct 111 ms 42488 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 8 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 8 ms 6528 KB Output is correct
11 Correct 164 ms 42552 KB Output is correct
12 Correct 35 ms 16000 KB Output is correct
13 Correct 55 ms 32376 KB Output is correct
14 Correct 652 ms 43124 KB Output is correct
15 Correct 111 ms 42488 KB Output is correct
16 Correct 152 ms 71160 KB Output is correct
17 Execution timed out 1587 ms 72816 KB Time limit exceeded
18 Halted 0 ms 0 KB -