oj.uz

Submission #93636

# Submission time Handle Problem Language Result Execution time Memory
93636 2019-01-10T13:33:53 Z tmwilliamlin168 Robots (APIO13_robots) C++14
100 / 100
 1002 ms 148216 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]) {
			if(d[u[0]][u[1]]<di)
				continue;
			for(int i=0; i<4; ++i) {
				array<int, 2> v=e[u[0]][u[1]][i];
				if(v[0]!=-2)
					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 119 ms 105104 KB Output is correct
2 Correct 123 ms 104972 KB Output is correct
3 Correct 115 ms 105080 KB Output is correct
4 Correct 114 ms 105084 KB Output is correct
5 Correct 122 ms 105128 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 105104 KB Output is correct
2 Correct 123 ms 104972 KB Output is correct
3 Correct 115 ms 105080 KB Output is correct
4 Correct 114 ms 105084 KB Output is correct
5 Correct 122 ms 105128 KB Output is correct
6 Correct 110 ms 105004 KB Output is correct
7 Correct 102 ms 105180 KB Output is correct
8 Correct 99 ms 105080 KB Output is correct
9 Correct 99 ms 105080 KB Output is correct
10 Correct 103 ms 105080 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 105104 KB Output is correct
2 Correct 123 ms 104972 KB Output is correct
3 Correct 115 ms 105080 KB Output is correct
4 Correct 114 ms 105084 KB Output is correct
5 Correct 122 ms 105128 KB Output is correct
6 Correct 110 ms 105004 KB Output is correct
7 Correct 102 ms 105180 KB Output is correct
8 Correct 99 ms 105080 KB Output is correct
9 Correct 99 ms 105080 KB Output is correct
10 Correct 103 ms 105080 KB Output is correct
11 Correct 570 ms 109948 KB Output is correct
12 Correct 89 ms 105720 KB Output is correct
13 Correct 326 ms 105364 KB Output is correct
14 Correct 720 ms 117380 KB Output is correct
15 Correct 537 ms 106680 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 105104 KB Output is correct
2 Correct 123 ms 104972 KB Output is correct
3 Correct 115 ms 105080 KB Output is correct
4 Correct 114 ms 105084 KB Output is correct
5 Correct 122 ms 105128 KB Output is correct
6 Correct 110 ms 105004 KB Output is correct
7 Correct 102 ms 105180 KB Output is correct
8 Correct 99 ms 105080 KB Output is correct
9 Correct 99 ms 105080 KB Output is correct
10 Correct 103 ms 105080 KB Output is correct
11 Correct 570 ms 109948 KB Output is correct
12 Correct 89 ms 105720 KB Output is correct
13 Correct 326 ms 105364 KB Output is correct
14 Correct 720 ms 117380 KB Output is correct
15 Correct 537 ms 106680 KB Output is correct
16 Correct 547 ms 105464 KB Output is correct
17 Correct 1002 ms 148216 KB Output is correct
18 Correct 534 ms 109552 KB Output is correct
19 Correct 486 ms 105464 KB Output is correct
20 Correct 869 ms 122384 KB Output is correct