oj.uz

Submission #734747

# Submission time Handle Problem Language Result Execution time Memory
734747 2023-05-03T03:40:12 Z SanguineChameleon Robots (APIO13_robots) C++17
30 / 100
 212 ms 111492 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;
	int prv = 0;
	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];
		assert(cd >= prv);
		prv = cd;
		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 46 ms 106064 KB Output is correct
2 Correct 47 ms 106096 KB Output is correct
3 Correct 46 ms 106108 KB Output is correct
4 Correct 47 ms 106104 KB Output is correct
5 Correct 45 ms 106060 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 106064 KB Output is correct
2 Correct 47 ms 106096 KB Output is correct
3 Correct 46 ms 106108 KB Output is correct
4 Correct 47 ms 106104 KB Output is correct
5 Correct 45 ms 106060 KB Output is correct
6 Correct 46 ms 106076 KB Output is correct
7 Correct 46 ms 106140 KB Output is correct
8 Correct 47 ms 106056 KB Output is correct
9 Correct 46 ms 106024 KB Output is correct
10 Correct 47 ms 106100 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 106064 KB Output is correct
2 Correct 47 ms 106096 KB Output is correct
3 Correct 46 ms 106108 KB Output is correct
4 Correct 47 ms 106104 KB Output is correct
5 Correct 45 ms 106060 KB Output is correct
6 Correct 46 ms 106076 KB Output is correct
7 Correct 46 ms 106140 KB Output is correct
8 Correct 47 ms 106056 KB Output is correct
9 Correct 46 ms 106024 KB Output is correct
10 Correct 47 ms 106100 KB Output is correct
11 Correct 109 ms 110956 KB Output is correct
12 Correct 50 ms 110104 KB Output is correct
13 Correct 63 ms 110288 KB Output is correct
14 Incorrect 212 ms 111492 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 106064 KB Output is correct
2 Correct 47 ms 106096 KB Output is correct
3 Correct 46 ms 106108 KB Output is correct
4 Correct 47 ms 106104 KB Output is correct
5 Correct 45 ms 106060 KB Output is correct
6 Correct 46 ms 106076 KB Output is correct
7 Correct 46 ms 106140 KB Output is correct
8 Correct 47 ms 106056 KB Output is correct
9 Correct 46 ms 106024 KB Output is correct
10 Correct 47 ms 106100 KB Output is correct
11 Correct 109 ms 110956 KB Output is correct
12 Correct 50 ms 110104 KB Output is correct
13 Correct 63 ms 110288 KB Output is correct
14 Incorrect 212 ms 111492 KB Output isn't correct
15 Halted 0 ms 0 KB -