oj.uz

Submission #93635

# Submission time Handle Problem Language Result Execution time Memory
93635 2019-01-10T13:28:00 Z tmwilliamlin168 Robots (APIO13_robots) C++14
100 / 100
 1219 ms 148604 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];

bool ib(int i, int j) {
	return i<0||j<0||i>=h||j>=w||g[i][j]=='x';
}

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]=ib(ni, nj)?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 123 ms 105080 KB Output is correct
2 Correct 116 ms 105080 KB Output is correct
3 Correct 99 ms 105072 KB Output is correct
4 Correct 104 ms 105088 KB Output is correct
5 Correct 102 ms 105060 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 105080 KB Output is correct
2 Correct 116 ms 105080 KB Output is correct
3 Correct 99 ms 105072 KB Output is correct
4 Correct 104 ms 105088 KB Output is correct
5 Correct 102 ms 105060 KB Output is correct
6 Correct 115 ms 105080 KB Output is correct
7 Correct 106 ms 105124 KB Output is correct
8 Correct 122 ms 105088 KB Output is correct
9 Correct 108 ms 105012 KB Output is correct
10 Correct 115 ms 105208 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 105080 KB Output is correct
2 Correct 116 ms 105080 KB Output is correct
3 Correct 99 ms 105072 KB Output is correct
4 Correct 104 ms 105088 KB Output is correct
5 Correct 102 ms 105060 KB Output is correct
6 Correct 115 ms 105080 KB Output is correct
7 Correct 106 ms 105124 KB Output is correct
8 Correct 122 ms 105088 KB Output is correct
9 Correct 108 ms 105012 KB Output is correct
10 Correct 115 ms 105208 KB Output is correct
11 Correct 545 ms 109828 KB Output is correct
12 Correct 107 ms 105692 KB Output is correct
13 Correct 353 ms 105208 KB Output is correct
14 Correct 721 ms 117368 KB Output is correct
15 Correct 619 ms 106716 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 105080 KB Output is correct
2 Correct 116 ms 105080 KB Output is correct
3 Correct 99 ms 105072 KB Output is correct
4 Correct 104 ms 105088 KB Output is correct
5 Correct 102 ms 105060 KB Output is correct
6 Correct 115 ms 105080 KB Output is correct
7 Correct 106 ms 105124 KB Output is correct
8 Correct 122 ms 105088 KB Output is correct
9 Correct 108 ms 105012 KB Output is correct
10 Correct 115 ms 105208 KB Output is correct
11 Correct 545 ms 109828 KB Output is correct
12 Correct 107 ms 105692 KB Output is correct
13 Correct 353 ms 105208 KB Output is correct
14 Correct 721 ms 117368 KB Output is correct
15 Correct 619 ms 106716 KB Output is correct
16 Correct 658 ms 105552 KB Output is correct
17 Correct 1219 ms 148604 KB Output is correct
18 Correct 614 ms 109808 KB Output is correct
19 Correct 576 ms 105764 KB Output is correct
20 Correct 768 ms 122768 KB Output is correct