oj.uz

Submission #734743

# Submission time Handle Problem Language Result Execution time Memory
734743 2023-05-03T03:29:46 Z SanguineChameleon Robots (APIO13_robots) C++17
60 / 100
 1500 ms 118096 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int inf = 1e9 + 20;
const int maxN = 5e2 + 20;
const int maxK = 10;
char grid[maxN][maxN];
int dp[maxK][maxK][maxN][maxN];
pair<int, int> nxt[maxN][maxN][4];

int N, M, K;

pair<int, int> calc(int cx, int cy, int d) {
	if (nxt[cx][cy][d].first == -2) {
		return (nxt[cx][cy][d] = make_pair(-1, -1));
	}
	if (nxt[cx][cy][d].first) {
		return nxt[cx][cy][d];
	}
	int nd = d;
	if (grid[cx][cy] == 'C') {
		nd = (nd + 1) % 4;
	}
	if (grid[cx][cy] == 'A') {
		nd = (nd + 3) % 4;
	}
	int nx = cx + dx[nd];
	int ny = cy + dy[nd];
	if (1 <= nx && nx <= N && 1 <= ny && ny <= M && grid[nx][ny] != 'x') {
		nxt[cx][cy][d] = make_pair(-2, -2);
		return (nxt[cx][cy][d] = calc(nx, ny, nd));
	}
	else {
		return (nxt[cx][cy][d] = make_pair(cx, cy));
	}
}

void dijkstra(int lt, int rt) {
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (dp[lt][rt][i][j] != inf) {
				q.emplace(dp[lt][rt][i][j], make_pair(i, j));
			}
		}
	}
	while (!q.empty()) {
		int cd = q.top().first;
		int cx = q.top().second.first;
		int cy = q.top().second.second;
		q.pop();
		if (dp[lt][rt][cx][cy] != cd) {
			continue;
		}
		for (int d = 0; d < 4; d++) {
			int nx = nxt[cx][cy][d].first;
			int ny = nxt[cx][cy][d].second;
			if (nx != -1 && dp[lt][rt][nx][ny] > cd + 1) {
				dp[lt][rt][nx][ny] = cd + 1;
				q.emplace(dp[lt][rt][nx][ny], make_pair(nx, ny));
			}
		}
	}
}

void just_do_it() {
	fill_n(&dp[0][0][0][0], maxK * maxK * maxN * maxN, inf);
	cin >> K >> M >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> grid[i][j];
			if ('1' <= grid[i][j] && grid[i][j] <= '9') {
				int d = grid[i][j] - '0';
				dp[d][d][i][j] = 0;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			for (int d = 0; d < 4; d++) {
				if (grid[i][j] == 'x') {
					nxt[i][j][d] = make_pair(-1, -1);
				}
				else {
					calc(i, j, d);
				}
			}
		}
	}
	for (int i = 1; i <= K; i++) {
		dijkstra(i, i);
	}
	for (int len = 2; len <= K; len++) {
		for (int i = 1, j = len; j <= K; i++, j++) {
			for (int x = 1; x <= N; x++) {
				for (int y = 1; y <= M; y++) {
					for (int k = i; k < j; k++) {
						dp[i][j][x][y] = min(dp[i][j][x][y], dp[i][k][x][y] + dp[k + 1][j][x][y]);
					}
				}
			}
			dijkstra(i, j);
		}
	}
	int res = inf;
	for (int x = 1; x <= N; x++) {
		for (int y = 1; y <= M; y++) {
			res = min(res, dp[1][K][x][y]);
		}
	}
	if (res == inf) {
		cout << -1;
	}
	else {
		cout << res;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 106076 KB Output is correct
2 Correct 51 ms 106044 KB Output is correct
3 Correct 47 ms 106076 KB Output is correct
4 Correct 46 ms 106148 KB Output is correct
5 Correct 46 ms 106188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 106076 KB Output is correct
2 Correct 51 ms 106044 KB Output is correct
3 Correct 47 ms 106076 KB Output is correct
4 Correct 46 ms 106148 KB Output is correct
5 Correct 46 ms 106188 KB Output is correct
6 Correct 46 ms 106148 KB Output is correct
7 Correct 45 ms 106092 KB Output is correct
8 Correct 52 ms 106120 KB Output is correct
9 Correct 46 ms 106168 KB Output is correct
10 Correct 47 ms 106136 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 106076 KB Output is correct
2 Correct 51 ms 106044 KB Output is correct
3 Correct 47 ms 106076 KB Output is correct
4 Correct 46 ms 106148 KB Output is correct
5 Correct 46 ms 106188 KB Output is correct
6 Correct 46 ms 106148 KB Output is correct
7 Correct 45 ms 106092 KB Output is correct
8 Correct 52 ms 106120 KB Output is correct
9 Correct 46 ms 106168 KB Output is correct
10 Correct 47 ms 106136 KB Output is correct
11 Correct 151 ms 110908 KB Output is correct
12 Correct 54 ms 110172 KB Output is correct
13 Correct 70 ms 110300 KB Output is correct
14 Correct 551 ms 111564 KB Output is correct
15 Correct 112 ms 110652 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 106076 KB Output is correct
2 Correct 51 ms 106044 KB Output is correct
3 Correct 47 ms 106076 KB Output is correct
4 Correct 46 ms 106148 KB Output is correct
5 Correct 46 ms 106188 KB Output is correct
6 Correct 46 ms 106148 KB Output is correct
7 Correct 45 ms 106092 KB Output is correct
8 Correct 52 ms 106120 KB Output is correct
9 Correct 46 ms 106168 KB Output is correct
10 Correct 47 ms 106136 KB Output is correct
11 Correct 151 ms 110908 KB Output is correct
12 Correct 54 ms 110172 KB Output is correct
13 Correct 70 ms 110300 KB Output is correct
14 Correct 551 ms 111564 KB Output is correct
15 Correct 112 ms 110652 KB Output is correct
16 Correct 110 ms 114756 KB Output is correct
17 Execution timed out 1515 ms 118096 KB Time limit exceeded
18 Halted 0 ms 0 KB -