oj.uz

Submission #93722

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

const int mxN=9, mxS=500, mxD=mxS*mxS*mxN/2;
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 80 ms 78584 KB Output is correct
2 Correct 77 ms 78584 KB Output is correct
3 Correct 78 ms 78584 KB Output is correct
4 Correct 75 ms 78588 KB Output is correct
5 Correct 80 ms 78584 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 78584 KB Output is correct
2 Correct 77 ms 78584 KB Output is correct
3 Correct 78 ms 78584 KB Output is correct
4 Correct 75 ms 78588 KB Output is correct
5 Correct 80 ms 78584 KB Output is correct
6 Correct 76 ms 78684 KB Output is correct
7 Correct 78 ms 78640 KB Output is correct
8 Correct 77 ms 78556 KB Output is correct
9 Correct 79 ms 78584 KB Output is correct
10 Correct 75 ms 78588 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 78584 KB Output is correct
2 Correct 77 ms 78584 KB Output is correct
3 Correct 78 ms 78584 KB Output is correct
4 Correct 75 ms 78588 KB Output is correct
5 Correct 80 ms 78584 KB Output is correct
6 Correct 76 ms 78684 KB Output is correct
7 Correct 78 ms 78640 KB Output is correct
8 Correct 77 ms 78556 KB Output is correct
9 Correct 79 ms 78584 KB Output is correct
10 Correct 75 ms 78588 KB Output is correct
11 Correct 394 ms 83448 KB Output is correct
12 Correct 77 ms 79224 KB Output is correct
13 Correct 232 ms 78844 KB Output is correct
14 Correct 526 ms 90972 KB Output is correct
15 Correct 323 ms 80376 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 78584 KB Output is correct
2 Correct 77 ms 78584 KB Output is correct
3 Correct 78 ms 78584 KB Output is correct
4 Correct 75 ms 78588 KB Output is correct
5 Correct 80 ms 78584 KB Output is correct
6 Correct 76 ms 78684 KB Output is correct
7 Correct 78 ms 78640 KB Output is correct
8 Correct 77 ms 78556 KB Output is correct
9 Correct 79 ms 78584 KB Output is correct
10 Correct 75 ms 78588 KB Output is correct
11 Correct 394 ms 83448 KB Output is correct
12 Correct 77 ms 79224 KB Output is correct
13 Correct 232 ms 78844 KB Output is correct
14 Correct 526 ms 90972 KB Output is correct
15 Correct 323 ms 80376 KB Output is correct
16 Correct 387 ms 78840 KB Output is correct
17 Correct 971 ms 121748 KB Output is correct
18 Correct 390 ms 83148 KB Output is correct
19 Correct 327 ms 79096 KB Output is correct
20 Correct 619 ms 96104 KB Output is correct