oj.uz

Submission #46916

# Submission time Handle Problem Language Result Execution time Memory
46916 2018-04-24T17:08:53 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();
 
	memset(dis, INF, sizeof dis);
	
	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 98 ms 138104 KB Output is correct
2 Correct 96 ms 138104 KB Output is correct
3 Correct 96 ms 138160 KB Output is correct
4 Correct 97 ms 138364 KB Output is correct
5 Correct 97 ms 138364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 138104 KB Output is correct
2 Correct 96 ms 138104 KB Output is correct
3 Correct 96 ms 138160 KB Output is correct
4 Correct 97 ms 138364 KB Output is correct
5 Correct 97 ms 138364 KB Output is correct
6 Correct 95 ms 138364 KB Output is correct
7 Correct 144 ms 138364 KB Output is correct
8 Correct 96 ms 138364 KB Output is correct
9 Correct 94 ms 138364 KB Output is correct
10 Correct 96 ms 138376 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 138104 KB Output is correct
2 Correct 96 ms 138104 KB Output is correct
3 Correct 96 ms 138160 KB Output is correct
4 Correct 97 ms 138364 KB Output is correct
5 Correct 97 ms 138364 KB Output is correct
6 Correct 95 ms 138364 KB Output is correct
7 Correct 144 ms 138364 KB Output is correct
8 Correct 96 ms 138364 KB Output is correct
9 Correct 94 ms 138364 KB Output is correct
10 Correct 96 ms 138376 KB Output is correct
11 Correct 175 ms 143476 KB Output is correct
12 Correct 112 ms 143476 KB Output is correct
13 Correct 128 ms 143476 KB Output is correct
14 Correct 254 ms 148964 KB Output is correct
15 Correct 158 ms 148964 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 138104 KB Output is correct
2 Correct 96 ms 138104 KB Output is correct
3 Correct 96 ms 138160 KB Output is correct
4 Correct 97 ms 138364 KB Output is correct
5 Correct 97 ms 138364 KB Output is correct
6 Correct 95 ms 138364 KB Output is correct
7 Correct 144 ms 138364 KB Output is correct
8 Correct 96 ms 138364 KB Output is correct
9 Correct 94 ms 138364 KB Output is correct
10 Correct 96 ms 138376 KB Output is correct
11 Correct 175 ms 143476 KB Output is correct
12 Correct 112 ms 143476 KB Output is correct
13 Correct 128 ms 143476 KB Output is correct
14 Correct 254 ms 148964 KB Output is correct
15 Correct 158 ms 148964 KB Output is correct
16 Correct 234 ms 148964 KB Output is correct
17 Execution timed out 1534 ms 163840 KB Time limit exceeded
18 Halted 0 ms 0 KB -