oj.uz

Submission #970344

# Submission time Handle Problem Language Result Execution time Memory
970344 2024-04-26T11:39:40 Z Halym2007 Robots (APIO13_robots) C++17
100 / 100
 1469 ms 121616 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], dp[N][N][10][10];
bool vis[N][N][10];
pii val[N][N][4];
 
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];
}
 
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 <= 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;
				}
			}
		}
	}
//	cout << dp[1][10][1][1];
//	return 0;
//			if (j == 2 and git == 2)
//			return cout << "ppp ->" << dp[1][1][2][2] << "\n", 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j + i - 1 <= n; ++j) {
			int git = j + i - 1;
			vector <vector <pii>> v(N * N + 5);
			if (i == 1) {
				for (int l = 1; l <= h; ++l) {
					for (int r = 1; r <= w; ++r) {
						if (int(a[l][r]-48) == j) {
							dp[l][r][j][j] = 0;
//							if (l == 1 and r == 1 and j == 1 and j == 1) {
//								cout << "mejow";
//								return 0;
//							}
							v[0].pb ({l, r});
						}
					}
				}
//				continue;
			}
//			if (j == 2 and git == 2)
//			return cout << "ppp ->" << dp[1][1][2][2] << "\n", 0;
//			if (j == 2 and git == 2) {
//				cout << dp[1][1][2][2];
//				return 0;
//			}
			else {
				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]);
//							if (l == 1 and r == 1 and j == 1 and git == 2 and !sym) {
//								cout << "kk - > " << sym << " " << dp[l];
//								return 0;
//							}
						}
						dp[l][r][j][git] = sym;
						if (sym < N * N) v[sym].pb ({l, r});
//						if (l == 1 and r == 1 and j == 1 and git == 2) {
//							cout << "kk - > " << sym;
//							return 0;
//						}
					}
				}
			}
//			if (j == 1 and git == 2) {
//				cout << dp[1][1][1][2];
//				return 0;
//			}
//			 tapmaly dp[l][r][j][git]
//			if (j == 2 and git == 2)
//			return cout << "ppp ->" << dp[1][1][2][2] << "\n", 0;
			
			for (int k = 0; 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 (x.ff == x.ss and x.ff == 1) {
//							cout << new_x.ff << " "  << new_x.ss << " " << dp[new_x.ff][new_x.ss][j][git] << " " << k << "\n";
////							return 0;
//						}
						if (new_x.ff != -1 and new_x.ss != -1) {
							if (dp[new_x.ff][new_x.ss][j][git] > k + 1) {
//								dp[x.ff][x.ss][j][git] = dp[new_x.ff][new_x.ss][j][git] + 1;
								dp[new_x.ff][new_x.ss][j][git] = k + 1;
								v[k + 1].pb ({new_x.ff, new_x.ss});
							}
						}
//						if (new_x.ff == 1 and new_x.ss == 10) {
//							cout << "menow : " << dp[1][10][1][1];
//							return 0;
//						}
//						assert (dp[1][10][1][1] != 0);
					}
				}
			}
//			if (j == 1 and git == 1)
//			return cout << "pppk ->" << dp[1][1][1][1] << "\n", 0;
//			return 0;
		}
	}
//	return cout << "oo - > " << dp[1][1][1][2], 0;
	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]);
//			cout << i << ' ' << j << ' ' << dp[i][j][1][2] << '\n';
		}
	}
	if (jogap == 1e9) jogap = -1;
	cout << jogap;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8448 KB Output is correct
2 Correct 5 ms 8448 KB Output is correct
3 Correct 5 ms 8448 KB Output is correct
4 Correct 5 ms 8540 KB Output is correct
5 Correct 5 ms 8540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8448 KB Output is correct
2 Correct 5 ms 8448 KB Output is correct
3 Correct 5 ms 8448 KB Output is correct
4 Correct 5 ms 8540 KB Output is correct
5 Correct 5 ms 8540 KB Output is correct
6 Correct 5 ms 8792 KB Output is correct
7 Correct 5 ms 8448 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 5 ms 8448 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8448 KB Output is correct
2 Correct 5 ms 8448 KB Output is correct
3 Correct 5 ms 8448 KB Output is correct
4 Correct 5 ms 8540 KB Output is correct
5 Correct 5 ms 8540 KB Output is correct
6 Correct 5 ms 8792 KB Output is correct
7 Correct 5 ms 8448 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 5 ms 8448 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct
11 Correct 275 ms 75196 KB Output is correct
12 Correct 18 ms 75096 KB Output is correct
13 Correct 101 ms 74984 KB Output is correct
14 Correct 448 ms 75748 KB Output is correct
15 Correct 204 ms 75000 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8448 KB Output is correct
2 Correct 5 ms 8448 KB Output is correct
3 Correct 5 ms 8448 KB Output is correct
4 Correct 5 ms 8540 KB Output is correct
5 Correct 5 ms 8540 KB Output is correct
6 Correct 5 ms 8792 KB Output is correct
7 Correct 5 ms 8448 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 5 ms 8448 KB Output is correct
10 Correct 4 ms 8540 KB Output is correct
11 Correct 275 ms 75196 KB Output is correct
12 Correct 18 ms 75096 KB Output is correct
13 Correct 101 ms 74984 KB Output is correct
14 Correct 448 ms 75748 KB Output is correct
15 Correct 204 ms 75000 KB Output is correct
16 Correct 398 ms 119148 KB Output is correct
17 Correct 1469 ms 121616 KB Output is correct
18 Correct 517 ms 119396 KB Output is correct
19 Correct 394 ms 119380 KB Output is correct
20 Correct 1102 ms 120224 KB Output is correct