oj.uz

Submission #46899

# Submission time Handle Problem Language Result Execution time Memory
46899 2018-04-24T15:59:45 Z minkank Robots (APIO13_robots) C++17
60 / 100
 1500 ms 163840 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 505;
const int M = 10;
const int INF = 1e9;

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};

struct State {
	int r, c, x, y, d;
};

int n, h, w;
int d1[M][M][N][N];
int d2[N][N][5][2];
char a[N][N];
vector<State> vec[N * N];

// A -1
// C +1

void bfs() {
	for (int i = 0; i <= w * h; ++i) {
		// cout << "#bfs-at " << i << '\n';
		while (vec[i].size()) {
			State u = vec[i].back(); vec[i].pop_back();
			if (u.d != d2[u.r][u.c][u.x][u.y]) continue;
			// cout << "#bfs-state " << u.r << ' ' << u.c << ' ' << u.x << ' ' << u.y << ' ' << u.d << '\n';
			if (u.x == 0) {
				for (int j = 0; j < 4; ++j) {
					State v = u;
					v.r += dr[j], v.c += dc[j], v.x = j + 1, v.y = 0, v.d++;
					if (v.r < 1 || v.c < 1 || v.r > h || v.c > w || a[v.r][v.c] == 'x') continue;
					if (d2[v.r][v.c][v.x][v.y] > v.d) {
						d2[v.r][v.c][v.x][v.y] = v.d, vec[v.d].push_back(v);
					}
				}
			}
			else {
				if (u.y == 0 && (a[u.r][u.c] == 'A' || a[u.r][u.c] == 'C')) {
					if (a[u.r][u.c] == 'A') {
						State v = u; v.x--, v.y = 1; if (v.x == 0) v.x = 4;
						if (d2[v.r][v.c][v.x][v.y] > v.d) {
							d2[v.r][v.c][v.x][v.y] = v.d, vec[v.d].push_back(v);
						}
					}
					else {
						State v = u; v.x++, v.y = 1; if (v.x == 5) v.x = 1;
						if (d2[v.r][v.c][v.x][v.y] > v.d) {
							d2[v.r][v.c][v.x][v.y] = v.d, vec[v.d].push_back(v);
						}
					}
				}
				else {
					State v = u; v.r += dr[v.x - 1], v.c += dc[v.x - 1], v.y = 0;
					if (v.r < 1 || v.c < 1 || v.r > h || v.c > w || a[v.r][v.c] == 'x') {
						v = u, v.x = v.y = 0;
						if (d2[v.r][v.c][v.x][v.y] > v.d) {
							d2[v.r][v.c][v.x][v.y] = v.d, vec[v.d].push_back(v);
						}
					}
					else {
						if (d2[v.r][v.c][v.x][v.y] > v.d) {
							d2[v.r][v.c][v.x][v.y] = v.d, vec[v.d].push_back(v);
						}
					}
				}
			}
		}
	}
}

void go(int l, int r) {
	for (int i = 0; i <= w * h; ++i) vec[i].clear();
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			for (int k = 0; k < 5; ++k) {
				for (int l = 0; l < 2; ++l) {
					d2[i][j][k][l] = INF;
				}
			}
			d2[i][j][0][0] = d1[l][r][i][j];
			if (d2[i][j][0][0] <= w * h) {
				vec[d2[i][j][0][0]].push_back({i, j, 0, 0, d2[i][j][0][0]});
			}
		}
	}
	bfs();
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			d1[l][r][i][j] = d2[i][j][0][0];
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> w >> h;
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			cin >> a[i][j];
		}
	}
	for (int l = 1; l <= n; ++l) {
		for (int r = l; r <= n; ++r) {
			for (int i = 1; i <= h; ++i) {
				for (int j = 1; j <= w; ++j) {
					d1[l][r][i][j] = INF;
				}
			}
		}
	}
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			if (a[i][j] >= '1' && a[i][j] <= '9') {
				int x = a[i][j] - '0';
				d1[x][x][i][j] = 0;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		go(i, i);
		// cout << "#at " << i << '\n';
		// for (int j = 1; j <= h; ++j) {
		// 	for (int k = 1; k <= w; ++k) {
		// 		cout << d1[i][i][j][k] << ' ';
		// 	}
		// 	cout << '\n';
		// }
	}
	for (int i = 2; i <= n; ++i) {
		for (int l = 1; l + i - 1 <= n; ++l) {
			int r = l + i - 1;
			for (int m = l; m < r; ++m) {
				for (int j = 1; j <= h; ++j) {
					for (int k = 1; k <= w; ++k) {
						d1[l][r][j][k] = min(d1[l][r][j][k], d1[l][m][j][k] + d1[m + 1][r][j][k]);
					}
				}
			}
			go(l, r);
		}
	}
	int res = INF;
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			res = min(res, d1[1][n][i][j]);
		}
	}
	if (res == INF) cout << -1; else cout << res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6356 KB Output is correct
2 Correct 6 ms 6504 KB Output is correct
3 Correct 8 ms 6504 KB Output is correct
4 Correct 8 ms 6504 KB Output is correct
5 Correct 7 ms 6604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6356 KB Output is correct
2 Correct 6 ms 6504 KB Output is correct
3 Correct 8 ms 6504 KB Output is correct
4 Correct 8 ms 6504 KB Output is correct
5 Correct 7 ms 6604 KB Output is correct
6 Correct 6 ms 6604 KB Output is correct
7 Correct 8 ms 6604 KB Output is correct
8 Correct 6 ms 6604 KB Output is correct
9 Correct 7 ms 6684 KB Output is correct
10 Correct 7 ms 6692 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6356 KB Output is correct
2 Correct 6 ms 6504 KB Output is correct
3 Correct 8 ms 6504 KB Output is correct
4 Correct 8 ms 6504 KB Output is correct
5 Correct 7 ms 6604 KB Output is correct
6 Correct 6 ms 6604 KB Output is correct
7 Correct 8 ms 6604 KB Output is correct
8 Correct 6 ms 6604 KB Output is correct
9 Correct 7 ms 6684 KB Output is correct
10 Correct 7 ms 6692 KB Output is correct
11 Correct 244 ms 59820 KB Output is correct
12 Correct 21 ms 59820 KB Output is correct
13 Correct 196 ms 59820 KB Output is correct
14 Correct 598 ms 65848 KB Output is correct
15 Correct 151 ms 65848 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6356 KB Output is correct
2 Correct 6 ms 6504 KB Output is correct
3 Correct 8 ms 6504 KB Output is correct
4 Correct 8 ms 6504 KB Output is correct
5 Correct 7 ms 6604 KB Output is correct
6 Correct 6 ms 6604 KB Output is correct
7 Correct 8 ms 6604 KB Output is correct
8 Correct 6 ms 6604 KB Output is correct
9 Correct 7 ms 6684 KB Output is correct
10 Correct 7 ms 6692 KB Output is correct
11 Correct 244 ms 59820 KB Output is correct
12 Correct 21 ms 59820 KB Output is correct
13 Correct 196 ms 59820 KB Output is correct
14 Correct 598 ms 65848 KB Output is correct
15 Correct 151 ms 65848 KB Output is correct
16 Correct 327 ms 65848 KB Output is correct
17 Execution timed out 1583 ms 163840 KB Time limit exceeded
18 Halted 0 ms 0 KB -