oj.uz

Submission #969999

# Submission time Handle Problem Language Result Execution time Memory
969999 2024-04-26T05:00:08 Z Halym2007 Robots (APIO13_robots) C++17
30 / 100
 1500 ms 124548 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5;
#define ff first
#define ss second
#define pii pair <int, int>
#define pb push_back
char a[N][N];
queue <pii> q;
 
// yokary saga asak cepe
int aa[] = {-1, 0, 1, 0};
int bb[] = {0, 1, 0, -1};
int n, h, w, state[N][N][4], dis[N][N][10], dp[N][N][10][10];
bool vis[N][N][10];
pii val[N][N][4];
vector <pii> v[N * N];
 
pii ugur (int x, int y, int typ) {
	if (a[x][y] == 'A') typ--;
	else if (a[x][y] == 'C') typ++;
	typ += 4;typ %= 4;
	if (state[x][y][typ] == 2) return val[x][y][typ];
	else if (state[x][y][typ] == 1) return {-1, -1};
	state[x][y][typ] = 1;
	int new_x = x + aa[typ], new_y = y + bb[typ];
	if (new_x < 1 or new_y < 1 or new_x > h or new_y > w or a[new_x][new_y] == 'x') val[x][y][typ] = {x, y};
	else val[x][y][typ] = ugur (new_x, new_y, typ);
	state[x][y][typ] = 2;
	return val[x][y][typ];
}
 
 
void solve (int x, int y, int typ) {
	dis[x][y][typ] = 0;
	vis[x][y][typ] = 1;
	q.push ({x, y});
	while (!q.empty()) {
		pii a1 = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {
			pii tr = ugur (a1.ff, a1.ss, i);
			if (tr.ff != -1 and tr.ss != -1) {
				if (vis[tr.ff][tr.ss][typ]) continue;
				vis[tr.ff][tr.ss][typ] = 1;
				dis[tr.ff][tr.ss][typ] = dis[a1.ff][a1.ss][typ] + 1;
				q.push({tr.ff, tr.ss});
			}
		}
	}
}
 
int main () {
	ios::sync_with_stdio(0);cin.tie(0);
//	freopen ("input.txt", "r", stdin);
	cin >> n >> w >> h;
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			for (int k = 1; k <= n; ++k) {
				dis[i][j][k] = 1e9;
			}
		}
	}
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			if (a[i][j] >= '1' and a[i][j] <= '9') {
				dis[i][j][int(a[i][j] - 48)] = 0;
				solve (i, j, int(a[i][j] - 48));
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			for (int l = 1; l <= h; ++l) {
				for (int r = 1; r <= w; ++r) {
					dp[l][r][i][j] = 1e9;
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j + i - 1 <= n; ++j) {
			int git = j + i - 1;
			if (i == 1) {
				for (int l = 1; l <= h; ++l) {
					for (int r = 1; r <= w; ++r) {
						dp[l][r][j][j] = dis[l][r][j];
					}
				}
				continue;
			}
			// tapmaly dp[l][r][j][git]
			for (int k = 0; k < N; ++k) v[i].clear();
			for (int l = 1; l <= h; ++l) {
				for (int r = 1; r <= w; ++r) {
					for (int k = j; k < git; ++k) {
						int sym = dp[l][r][j][k] + dp[l][r][k + 1][git];
						dp[l][r][j][git] = min (dp[l][r][j][git], sym);
						if (sym < N * N) 
							v[sym].pb ({l, r});
					}
				}
			}
			for (int k = 1; k < N * N; ++k) {
				for (pii x : v[k]) {
					for (int l = 0; l < 4; ++l) {
						pii new_x = ugur (x.ff, x.ss, l);
						if (new_x.ff != -1 and new_x.ss != -1) {
							if (k  > dp[new_x.ff][new_x.ss][j][git] + 1) {
								dp[x.ff][x.ss][j][git] = min (dp[x.ff][x.ss][j][git], dp[new_x.ff][new_x.ss][j][git] + 1);
							}
						}
					}
				}
			}
		}
	}
	int jogap = 1e9;
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			jogap = min (jogap, dp[i][j][1][n]);
		}
	}
	if (jogap == 1e9) jogap = -1;
	cout << jogap;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13144 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 13044 KB Output is correct
4 Correct 3 ms 13144 KB Output is correct
5 Correct 3 ms 12960 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13144 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 13044 KB Output is correct
4 Correct 3 ms 13144 KB Output is correct
5 Correct 3 ms 12960 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13144 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 13044 KB Output is correct
4 Correct 3 ms 13144 KB Output is correct
5 Correct 3 ms 12960 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 1167 ms 104816 KB Output is correct
12 Correct 17 ms 85596 KB Output is correct
13 Correct 89 ms 85340 KB Output is correct
14 Execution timed out 1571 ms 124548 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13144 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 13044 KB Output is correct
4 Correct 3 ms 13144 KB Output is correct
5 Correct 3 ms 12960 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 1167 ms 104816 KB Output is correct
12 Correct 17 ms 85596 KB Output is correct
13 Correct 89 ms 85340 KB Output is correct
14 Execution timed out 1571 ms 124548 KB Time limit exceeded
15 Halted 0 ms 0 KB -