oj.uz

Submission #46918

# Submission time Handle Problem Language Result Execution time Memory
46918 2018-04-24T17:33:43 Z minkank Robots (APIO13_robots) C++17
60 / 100
 1500 ms 163840 KB 
#include <bits/stdc++.h>
 
#define fi first
#define se second
 
using namespace std;
 
const int N = 505;
const int M = 10;
const int INF = 0x3f3f3f3f;
 
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
 
struct State {
	pair<int, int> p;
	int x, y;
 
	State() {}
 
	State (pair<int, int> p, int x, int y) :
		p(p), x(x), y(y) {}
};
 
int n, h, w;
int dis[M][M][N][N];
State nxt[N][N][4][2];
bool visit[N][N][4][2];
char a[N][N];
vector< pair<int, int> > vec[N * N];
 
// A -1
// C +1
 
State dfs(int r, int c, int x, int y) {
	if (visit[r][c][x][y]) return nxt[r][c][x][y];
	visit[r][c][x][y] = 1;
	if (y == 0 && (a[r][c] == 'A' || a[r][c] == 'C')) {
		int nx = x;
		if (a[r][c] == 'A') {
			nx--; if (nx == -1) nx = 3;
		}
		else {
			nx++; if (nx == 4) nx = 0;
		}
		return nxt[r][c][x][y] = dfs(r, c, nx, 1);
	}
	else {
		int nr, nc;
		nr = r + dr[x], nc = c + dc[x];
		if (nr < 1 || nc < 1 || nr > h || nc > w || a[nr][nc] == 'x') {
			return nxt[r][c][x][y] = State({r, c}, x, y);
		}
		else {
			return nxt[r][c][x][y] = dfs(nr, nc, x, 0);
		}
	}
}
 
void bfs(int l, int r) {
	for (int i = 0; i <= w * h; ++i) {
		while (vec[i].size()) {
			pair<int, int> u = vec[i].back(); vec[i].pop_back();
			if (dis[l][r][u.fi][u.se] != i) continue;
			for (int j = 0; j < 4; ++j) {
				pair<int, int> v = nxt[u.fi][u.se][j][1].p;
				if (dis[l][r][v.fi][v.se] > i + 1) {
					dis[l][r][v.fi][v.se] = i + 1, vec[i + 1].push_back(v);
				}
			}
		}
	}
}
 
void go(int l, int r) {
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			if (dis[l][r][i][j] <= w * h) {
				vec[dis[l][r][i][j]].push_back({i, j});
			}
		}
	}
	bfs(l, r);
}
 
int main() {
	cin >> n >> w >> h; getchar();
 
	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) {
					dis[l][r][i][j] = INF;
				}
			}
		}
	}
	
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			a[i][j] = getchar();
			if (a[i][j] >= '1' && a[i][j] <= '9') {
				int x = a[i][j] - '0';
				dis[x][x][i][j] = 0;
			}
		}		
		getchar();
	}
 
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			for (int k = 0; k < 4; ++k) {
				dfs(i, j, k, 1);
				// cout << "#nxt " << i << ' ' << j << ' ' << k << ":\n";
				// cout << nxt[i][j][k][1].p.fi << ' ' << nxt[i][j][k][1].p.se << '\n';
			}
		}
	}
 
	for (int i = 1; i <= n; ++i) go(i, i);
 
	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) {
						dis[l][r][j][k] = min(dis[l][r][j][k], dis[l][m][j][k] + dis[m + 1][r][j][k]);
					}
				}
			}
			go(l, r);
		}
	}
 
	// for (int l = 1; l <= n; ++l) {
	// 	for (int r = l; r <= n; ++r) {
	// 		cout << "#at " << l << ' ' << r << '\n';
	// 		for (int i = 1; i <= h; ++i) {
	// 			for (int j = 1; j <= w; ++j) {
	// 				cout << dis[l][r][i][j] << ' ';
	// 			}
	// 			cout << '\n';
	// 		}
	// 	}
	// }
 
	int res = INF;
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			res = min(res, dis[1][n][i][j]);
		}
	}
	if (res == INF) cout << -1; else cout << res;
 
	// cerr << '\n' << clock() * 1000 / CLOCKS_PER_SEC;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 38264 KB Output is correct
2 Correct 27 ms 38376 KB Output is correct
3 Correct 28 ms 38376 KB Output is correct
4 Correct 28 ms 38452 KB Output is correct
5 Correct 33 ms 38512 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 38264 KB Output is correct
2 Correct 27 ms 38376 KB Output is correct
3 Correct 28 ms 38376 KB Output is correct
4 Correct 28 ms 38452 KB Output is correct
5 Correct 33 ms 38512 KB Output is correct
6 Correct 27 ms 38512 KB Output is correct
7 Correct 27 ms 38512 KB Output is correct
8 Correct 28 ms 38512 KB Output is correct
9 Correct 27 ms 38560 KB Output is correct
10 Correct 27 ms 38576 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 38264 KB Output is correct
2 Correct 27 ms 38376 KB Output is correct
3 Correct 28 ms 38376 KB Output is correct
4 Correct 28 ms 38452 KB Output is correct
5 Correct 33 ms 38512 KB Output is correct
6 Correct 27 ms 38512 KB Output is correct
7 Correct 27 ms 38512 KB Output is correct
8 Correct 28 ms 38512 KB Output is correct
9 Correct 27 ms 38560 KB Output is correct
10 Correct 27 ms 38576 KB Output is correct
11 Correct 131 ms 70436 KB Output is correct
12 Correct 47 ms 70436 KB Output is correct
13 Correct 69 ms 70436 KB Output is correct
14 Correct 196 ms 75568 KB Output is correct
15 Correct 107 ms 75568 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 38264 KB Output is correct
2 Correct 27 ms 38376 KB Output is correct
3 Correct 28 ms 38376 KB Output is correct
4 Correct 28 ms 38452 KB Output is correct
5 Correct 33 ms 38512 KB Output is correct
6 Correct 27 ms 38512 KB Output is correct
7 Correct 27 ms 38512 KB Output is correct
8 Correct 28 ms 38512 KB Output is correct
9 Correct 27 ms 38560 KB Output is correct
10 Correct 27 ms 38576 KB Output is correct
11 Correct 131 ms 70436 KB Output is correct
12 Correct 47 ms 70436 KB Output is correct
13 Correct 69 ms 70436 KB Output is correct
14 Correct 196 ms 75568 KB Output is correct
15 Correct 107 ms 75568 KB Output is correct
16 Correct 203 ms 85932 KB Output is correct
17 Execution timed out 1555 ms 163840 KB Time limit exceeded
18 Halted 0 ms 0 KB -