oj.uz

Submission #734746

# Submission time Handle Problem Language Result Execution time Memory
734746 2023-05-03T03:38:19 Z SanguineChameleon Robots (APIO13_robots) C++17
30 / 100
 225 ms 111520 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;
	Q.emplace_back(S[0].second);
	int pt = 1;
	while (!Q.empty()) {
		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();
		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_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 106052 KB Output is correct
2 Correct 57 ms 106096 KB Output is correct
3 Correct 52 ms 106020 KB Output is correct
4 Correct 46 ms 106188 KB Output is correct
5 Correct 47 ms 106112 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 106052 KB Output is correct
2 Correct 57 ms 106096 KB Output is correct
3 Correct 52 ms 106020 KB Output is correct
4 Correct 46 ms 106188 KB Output is correct
5 Correct 47 ms 106112 KB Output is correct
6 Correct 47 ms 106144 KB Output is correct
7 Correct 48 ms 106100 KB Output is correct
8 Correct 51 ms 106116 KB Output is correct
9 Correct 48 ms 106060 KB Output is correct
10 Correct 49 ms 106196 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 106052 KB Output is correct
2 Correct 57 ms 106096 KB Output is correct
3 Correct 52 ms 106020 KB Output is correct
4 Correct 46 ms 106188 KB Output is correct
5 Correct 47 ms 106112 KB Output is correct
6 Correct 47 ms 106144 KB Output is correct
7 Correct 48 ms 106100 KB Output is correct
8 Correct 51 ms 106116 KB Output is correct
9 Correct 48 ms 106060 KB Output is correct
10 Correct 49 ms 106196 KB Output is correct
11 Correct 133 ms 110888 KB Output is correct
12 Correct 65 ms 110188 KB Output is correct
13 Correct 66 ms 110200 KB Output is correct
14 Incorrect 225 ms 111520 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 106052 KB Output is correct
2 Correct 57 ms 106096 KB Output is correct
3 Correct 52 ms 106020 KB Output is correct
4 Correct 46 ms 106188 KB Output is correct
5 Correct 47 ms 106112 KB Output is correct
6 Correct 47 ms 106144 KB Output is correct
7 Correct 48 ms 106100 KB Output is correct
8 Correct 51 ms 106116 KB Output is correct
9 Correct 48 ms 106060 KB Output is correct
10 Correct 49 ms 106196 KB Output is correct
11 Correct 133 ms 110888 KB Output is correct
12 Correct 65 ms 110188 KB Output is correct
13 Correct 66 ms 110200 KB Output is correct
14 Incorrect 225 ms 111520 KB Output isn't correct
15 Halted 0 ms 0 KB -