oj.uz

Submission #93723

# Submission time Handle Problem Language Result Execution time Memory
93723 2019-01-10T22:43:36 Z nikolapesic2802 Robots (APIO13_robots) C++14
100 / 100
 790 ms 101296 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=9, mxS=500, mxD=mxS*mxS;
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 51 ms 58104 KB Output is correct
2 Correct 48 ms 58104 KB Output is correct
3 Correct 49 ms 58104 KB Output is correct
4 Correct 50 ms 58040 KB Output is correct
5 Correct 49 ms 58104 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 58104 KB Output is correct
2 Correct 48 ms 58104 KB Output is correct
3 Correct 49 ms 58104 KB Output is correct
4 Correct 50 ms 58040 KB Output is correct
5 Correct 49 ms 58104 KB Output is correct
6 Correct 49 ms 58104 KB Output is correct
7 Correct 49 ms 58104 KB Output is correct
8 Correct 50 ms 58104 KB Output is correct
9 Correct 50 ms 58076 KB Output is correct
10 Correct 48 ms 58104 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 58104 KB Output is correct
2 Correct 48 ms 58104 KB Output is correct
3 Correct 49 ms 58104 KB Output is correct
4 Correct 50 ms 58040 KB Output is correct
5 Correct 49 ms 58104 KB Output is correct
6 Correct 49 ms 58104 KB Output is correct
7 Correct 49 ms 58104 KB Output is correct
8 Correct 50 ms 58104 KB Output is correct
9 Correct 50 ms 58076 KB Output is correct
10 Correct 48 ms 58104 KB Output is correct
11 Correct 164 ms 62840 KB Output is correct
12 Correct 54 ms 58752 KB Output is correct
13 Correct 86 ms 58288 KB Output is correct
14 Correct 266 ms 70364 KB Output is correct
15 Correct 118 ms 59720 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 58104 KB Output is correct
2 Correct 48 ms 58104 KB Output is correct
3 Correct 49 ms 58104 KB Output is correct
4 Correct 50 ms 58040 KB Output is correct
5 Correct 49 ms 58104 KB Output is correct
6 Correct 49 ms 58104 KB Output is correct
7 Correct 49 ms 58104 KB Output is correct
8 Correct 50 ms 58104 KB Output is correct
9 Correct 50 ms 58076 KB Output is correct
10 Correct 48 ms 58104 KB Output is correct
11 Correct 164 ms 62840 KB Output is correct
12 Correct 54 ms 58752 KB Output is correct
13 Correct 86 ms 58288 KB Output is correct
14 Correct 266 ms 70364 KB Output is correct
15 Correct 118 ms 59720 KB Output is correct
16 Correct 154 ms 58464 KB Output is correct
17 Correct 790 ms 101296 KB Output is correct
18 Correct 187 ms 62576 KB Output is correct
19 Correct 153 ms 58472 KB Output is correct
20 Correct 408 ms 75440 KB Output is correct