oj.uz

Submission #46913

# Submission time Handle Problem Language Result Execution time Memory
46913 2018-04-24T16:57:18 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 = 0; i <= w * h; ++i) vec[i].clear();
	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() {
	ios::sync_with_stdio(false);

	cin >> n >> w >> h;

	memset(dis, INF, sizeof dis);
	
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			cin >> a[i][j];
			if (a[i][j] >= '1' && a[i][j] <= '9') {
				int x = a[i][j] - '0';
				dis[x][x][i][j] = 0;
			}
		}		
	}

	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 << clock() * 1000 / CLOCKS_PER_SEC;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 138104 KB Output is correct
2 Correct 96 ms 138156 KB Output is correct
3 Correct 96 ms 138340 KB Output is correct
4 Correct 97 ms 138340 KB Output is correct
5 Correct 95 ms 138340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 138104 KB Output is correct
2 Correct 96 ms 138156 KB Output is correct
3 Correct 96 ms 138340 KB Output is correct
4 Correct 97 ms 138340 KB Output is correct
5 Correct 95 ms 138340 KB Output is correct
6 Correct 95 ms 138340 KB Output is correct
7 Correct 95 ms 138340 KB Output is correct
8 Correct 112 ms 138340 KB Output is correct
9 Correct 111 ms 138340 KB Output is correct
10 Correct 160 ms 138408 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 138104 KB Output is correct
2 Correct 96 ms 138156 KB Output is correct
3 Correct 96 ms 138340 KB Output is correct
4 Correct 97 ms 138340 KB Output is correct
5 Correct 95 ms 138340 KB Output is correct
6 Correct 95 ms 138340 KB Output is correct
7 Correct 95 ms 138340 KB Output is correct
8 Correct 112 ms 138340 KB Output is correct
9 Correct 111 ms 138340 KB Output is correct
10 Correct 160 ms 138408 KB Output is correct
11 Correct 183 ms 143552 KB Output is correct
12 Correct 113 ms 143552 KB Output is correct
13 Correct 136 ms 143552 KB Output is correct
14 Correct 265 ms 148972 KB Output is correct
15 Correct 170 ms 148972 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 138104 KB Output is correct
2 Correct 96 ms 138156 KB Output is correct
3 Correct 96 ms 138340 KB Output is correct
4 Correct 97 ms 138340 KB Output is correct
5 Correct 95 ms 138340 KB Output is correct
6 Correct 95 ms 138340 KB Output is correct
7 Correct 95 ms 138340 KB Output is correct
8 Correct 112 ms 138340 KB Output is correct
9 Correct 111 ms 138340 KB Output is correct
10 Correct 160 ms 138408 KB Output is correct
11 Correct 183 ms 143552 KB Output is correct
12 Correct 113 ms 143552 KB Output is correct
13 Correct 136 ms 143552 KB Output is correct
14 Correct 265 ms 148972 KB Output is correct
15 Correct 170 ms 148972 KB Output is correct
16 Correct 252 ms 148972 KB Output is correct
17 Execution timed out 1592 ms 163840 KB Time limit exceeded
18 Halted 0 ms 0 KB -