oj.uz

Submission #93716

# Submission time Handle Problem Language Result Execution time Memory
93716 2019-01-10T22:25:28 Z nikolapesic2802 Robots (APIO13_robots) C++14
100 / 100
 1308 ms 148144 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=9, mxS=500, mxD=mxS*mxS*mxN;
int n, w, h, di[4]={-1, 0, 1, 0}, dj[4]={0, 1, 0, -1}, d[mxN*(mxN+1)/2][mxS][mxS], ans=INT_MAX, m1[mxN][mxN];
string g[mxS];
array<int, 2> e[mxS][mxS][4], m2[mxN*(mxN+1)/2];
vector<array<int, 2>> bd[mxD];

array<int, 2> dfs(int i, int j, int k) {
	if(e[i][j][k][0]==-1) {
		e[i][j][k][0]=-2;
		int nk=k;
		if(g[i][j]=='C')
			nk=(k+1)%4;
		else if(g[i][j]=='A')
			nk=(k+3)%4;
		int ni=i+di[nk], nj=j+dj[nk];
		e[i][j][k]=ni<0||ni>=h||nj<0||nj>=w||g[ni][nj]=='x'?array<int, 2>{i, j}:dfs(ni, nj, nk);
	}
	return e[i][j][k];
}

void ud(int d[mxS][mxS], int i, int j, int k) {
	if(k<mxD&&d[i][j]>k) {
		d[i][j]=k;
		bd[k].push_back({i, j});
	}
}

void bfs(int d[mxS][mxS]) {
	for(int di=0; di<mxD; ++di) {
		for(array<int, 2> u : bd[di]) {
			for(int i=0; i<4; ++i) {
				array<int, 2> v=e[u[0]][u[1]][i];
				ud(d, v[0], v[1], di+1);
			}
		}
		bd[di].clear();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> w >> h;
	for(int i=0; i<h; ++i)
		cin >> g[i];
	memset(e, -1, sizeof(e));
	for(int i=0; i<h; ++i)
		for(int j=0; j<w; ++j)
			for(int k=0; k<4; ++k)
				dfs(i, j, k);
	memset(d, 0x3f, sizeof(d));
	for(int i=0, k=0; i<n; ++i) {
		for(int j=i; j>=0; --j, ++k) {
			m1[j][i]=k;
			m2[k]={j, i};
			if(j<i) {
				for(int x=0; x<h; ++x)
					for(int y=0; y<w; ++y)
						for(int l=j; l<i; ++l)
							ud(d[k], x, y, d[m1[j][l]][x][y]+d[m1[l+1][i]][x][y]);
			} else
				for(int x=0; x<h; ++x)
					for(int y=0; y<w; ++y)
						if(g[x][y]-'0'-1==j)
							ud(d[k], x, y, 0);
			bfs(d[k]);
		}
	}
	for(int i=0; i<h; ++i)
		for(int j=0; j<w; ++j)
			ans=min(d[m1[0][n-1]][i][j], ans);
	cout << (ans>1e9?-1:ans);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 105080 KB Output is correct
2 Correct 117 ms 105088 KB Output is correct
3 Correct 121 ms 105080 KB Output is correct
4 Correct 117 ms 105208 KB Output is correct
5 Correct 117 ms 105080 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 105080 KB Output is correct
2 Correct 117 ms 105088 KB Output is correct
3 Correct 121 ms 105080 KB Output is correct
4 Correct 117 ms 105208 KB Output is correct
5 Correct 117 ms 105080 KB Output is correct
6 Correct 115 ms 105080 KB Output is correct
7 Correct 116 ms 105080 KB Output is correct
8 Correct 115 ms 105052 KB Output is correct
9 Correct 116 ms 105096 KB Output is correct
10 Correct 121 ms 105044 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 105080 KB Output is correct
2 Correct 117 ms 105088 KB Output is correct
3 Correct 121 ms 105080 KB Output is correct
4 Correct 117 ms 105208 KB Output is correct
5 Correct 117 ms 105080 KB Output is correct
6 Correct 115 ms 105080 KB Output is correct
7 Correct 116 ms 105080 KB Output is correct
8 Correct 115 ms 105052 KB Output is correct
9 Correct 116 ms 105096 KB Output is correct
10 Correct 121 ms 105044 KB Output is correct
11 Correct 663 ms 109816 KB Output is correct
12 Correct 106 ms 105720 KB Output is correct
13 Correct 358 ms 105136 KB Output is correct
14 Correct 762 ms 117372 KB Output is correct
15 Correct 615 ms 106716 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 105080 KB Output is correct
2 Correct 117 ms 105088 KB Output is correct
3 Correct 121 ms 105080 KB Output is correct
4 Correct 117 ms 105208 KB Output is correct
5 Correct 117 ms 105080 KB Output is correct
6 Correct 115 ms 105080 KB Output is correct
7 Correct 116 ms 105080 KB Output is correct
8 Correct 115 ms 105052 KB Output is correct
9 Correct 116 ms 105096 KB Output is correct
10 Correct 121 ms 105044 KB Output is correct
11 Correct 663 ms 109816 KB Output is correct
12 Correct 106 ms 105720 KB Output is correct
13 Correct 358 ms 105136 KB Output is correct
14 Correct 762 ms 117372 KB Output is correct
15 Correct 615 ms 106716 KB Output is correct
16 Correct 579 ms 105424 KB Output is correct
17 Correct 1308 ms 148144 KB Output is correct
18 Correct 666 ms 109476 KB Output is correct
19 Correct 633 ms 105476 KB Output is correct
20 Correct 872 ms 122456 KB Output is correct