oj.uz

Submission #734748

# Submission time Handle Problem Language Result Execution time Memory
734748 2023-05-03T03:42:52 Z SanguineChameleon Robots (APIO13_robots) C++17
100 / 100
 572 ms 117900 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) {
	vector<pair<int, pair<int, int>>> S;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (dp[lt][rt][i][j] != inf) {
				S.emplace_back(dp[lt][rt][i][j], make_pair(i, j));
			}
		}
	}
	if (S.empty()) {
		return;
	}
	sort(S.begin(), S.end());
	deque<pair<int, int>> Q;
	int pt = 0;
	while (!Q.empty() || pt < (int)S.size()) {
		if (Q.empty()) {
			int nx = S[pt].second.first;
			int ny = S[pt].second.second;
			if (dp[lt][rt][nx][ny] == S[pt].first) {
				Q.emplace_back(nx, ny);
			}
			pt++;
			continue;
		}
		int cx = Q.front().first;
		int cy = Q.front().second;
		int cd = dp[lt][rt][cx][cy];
		while (pt < (int)S.size() && S[pt].first <= cd) {
			int nx = S[pt].second.first;
			int ny = S[pt].second.second;
			if (dp[lt][rt][nx][ny] == S[pt].first) {
				Q.emplace_front(nx, ny);
			}
			pt++;
		}
		cx = Q.front().first;
		cy = Q.front().second;
		cd = dp[lt][rt][cx][cy];
		Q.pop_front();
		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_back(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 45 ms 106040 KB Output is correct
2 Correct 47 ms 106132 KB Output is correct
3 Correct 46 ms 106112 KB Output is correct
4 Correct 46 ms 106184 KB Output is correct
5 Correct 47 ms 106084 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 106040 KB Output is correct
2 Correct 47 ms 106132 KB Output is correct
3 Correct 46 ms 106112 KB Output is correct
4 Correct 46 ms 106184 KB Output is correct
5 Correct 47 ms 106084 KB Output is correct
6 Correct 48 ms 106120 KB Output is correct
7 Correct 46 ms 106096 KB Output is correct
8 Correct 47 ms 106148 KB Output is correct
9 Correct 45 ms 106100 KB Output is correct
10 Correct 45 ms 106188 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 106040 KB Output is correct
2 Correct 47 ms 106132 KB Output is correct
3 Correct 46 ms 106112 KB Output is correct
4 Correct 46 ms 106184 KB Output is correct
5 Correct 47 ms 106084 KB Output is correct
6 Correct 48 ms 106120 KB Output is correct
7 Correct 46 ms 106096 KB Output is correct
8 Correct 47 ms 106148 KB Output is correct
9 Correct 45 ms 106100 KB Output is correct
10 Correct 45 ms 106188 KB Output is correct
11 Correct 117 ms 110976 KB Output is correct
12 Correct 52 ms 110120 KB Output is correct
13 Correct 64 ms 110284 KB Output is correct
14 Correct 234 ms 111564 KB Output is correct
15 Correct 87 ms 110580 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 106040 KB Output is correct
2 Correct 47 ms 106132 KB Output is correct
3 Correct 46 ms 106112 KB Output is correct
4 Correct 46 ms 106184 KB Output is correct
5 Correct 47 ms 106084 KB Output is correct
6 Correct 48 ms 106120 KB Output is correct
7 Correct 46 ms 106096 KB Output is correct
8 Correct 47 ms 106148 KB Output is correct
9 Correct 45 ms 106100 KB Output is correct
10 Correct 45 ms 106188 KB Output is correct
11 Correct 117 ms 110976 KB Output is correct
12 Correct 52 ms 110120 KB Output is correct
13 Correct 64 ms 110284 KB Output is correct
14 Correct 234 ms 111564 KB Output is correct
15 Correct 87 ms 110580 KB Output is correct
16 Correct 118 ms 114572 KB Output is correct
17 Correct 572 ms 117900 KB Output is correct
18 Correct 143 ms 116404 KB Output is correct
19 Correct 105 ms 114776 KB Output is correct
20 Correct 329 ms 117416 KB Output is correct