oj.uz

Submission #970001

# Submission time Handle Problem Language Result Execution time Memory
970001 2024-04-26T05:07:45 Z Halym2007 Robots (APIO13_robots) C++17
30 / 100
 1500 ms 104400 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 = (typ + 3) % 4;
	else if (a[x][y] == 'C') typ = (typ + 1) % 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) {
				int sym = 1e9;
					for (int k = j; k < git; ++k) {
						sym = min (sym, dp[l][r][j][k] + dp[l][r][k + 1][git]);
					}
					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 4 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 13044 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 13044 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 2 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 4 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 13044 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 584 ms 90444 KB Output is correct
12 Correct 17 ms 84572 KB Output is correct
13 Correct 86 ms 84316 KB Output is correct
14 Execution timed out 1504 ms 104400 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 13044 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 3 ms 12888 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 584 ms 90444 KB Output is correct
12 Correct 17 ms 84572 KB Output is correct
13 Correct 86 ms 84316 KB Output is correct
14 Execution timed out 1504 ms 104400 KB Time limit exceeded
15 Halted 0 ms 0 KB -