Submission #734746

#	Time	Username	Problem	Language	Result	Execution time	Memory
734746		SanguineChameleon	Robots (APIO13_robots)	C++17	30 / 100	225 ms	111520 KiB

robots

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40