oj.uz

Submission #500728

# Submission time Handle Problem Language Result Execution time Memory
500728 2022-01-01T00:09:39 Z super_j6 Robots (APIO13_robots) C++14
60 / 100
 544 ms 96300 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 300, mxk = 9, w = 4, mxz = mxn * mxn * w;
const int dx[w] = {1, 0, -1, 0}, dy[w] = {0, 1, 0, -1};
int n, m, k, z;
char a[mxn][mxn];
int b[mxz], d[mxz], h[mxk][mxk], dp[mxk * (mxk + 1) / 2][mxz];
vector<int> g[mxz], q[mxz];

int f(int x, int y, int e){ return x * m * w + y * w + e;}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> k >> m >> n;
	z = n * m * w;
	
	for(int i = 0; i < n; i++)
	for(int j = 0; j < m; j++){
		cin >> a[i][j];
	}
	
	for(int i = k - 1, x = 0; ~i; i--)
	for(int j = i; j < k; j++){
		h[i][j] = x++;
	}
	
	memset(dp, 0x3f, sizeof(dp));
	for(int i = 0; i < n; i++)
	for(int j = 0; j < m; j++) if(a[i][j] != 'x')
	for(int l = 0; l < w; l++){
		int e = (l + (a[i][j] == 'A' ? 1 : a[i][j] == 'C' ? w - 1 : 0)) % w;
		int x = i + dx[e], y = j + dy[e], u = f(i, j, l);
		if(x >= 0 && y >= 0 && x < n && y < m && a[x][y] != 'x'){
			g[u].push_back(f(x, y, e));
		}else{
			b[u] = 1;
			for(int p = 0; p < w; p++) if(l != p) g[u].push_back(f(i, j, p));
		}
		if(isdigit(a[i][j])){
			int x = a[i][j] - '1';
			dp[h[x][x]][u] = 0;
		}
	}
	
	for(int i = k - 1; ~i; i--)
	for(int j = i; j < k; j++){
		int hh = h[i][j];
		for(int l = 0; l < z; l++) q[l].clear();
		for(int l = 0; l < z; l++){
			d[l] = 0;
			if(b[l]) for(int p = i; p < j; p++){
				dp[hh][l] = min(dp[hh][l], dp[h[i][p]][l] + dp[h[p + 1][j]][l]);
			}
			if(dp[hh][l] < z) q[dp[hh][l]].push_back(l);
		}
		for(int l = 0; l < z; l++)
		while(!q[l].empty()){
			int c = q[l].back();
			q[l].pop_back();
			if(d[c]) continue;
			d[c] = 1;
			for(int p : g[c]){
				int x = l + (c / w != p / w && b[p]);
				if(dp[hh][p] > x) q[dp[hh][p] = x].push_back(p);
			}
		}
	}
	
	int ret = *min_element(dp[h[0][k - 1]], dp[h[0][k - 1]] + z);
	
	cout << (ret < z ? ret : -1) << endl;
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 80588 KB Output is correct
2 Correct 35 ms 80560 KB Output is correct
3 Correct 33 ms 80588 KB Output is correct
4 Correct 32 ms 80632 KB Output is correct
5 Correct 33 ms 80580 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 80588 KB Output is correct
2 Correct 35 ms 80560 KB Output is correct
3 Correct 33 ms 80588 KB Output is correct
4 Correct 32 ms 80632 KB Output is correct
5 Correct 33 ms 80580 KB Output is correct
6 Correct 33 ms 80576 KB Output is correct
7 Correct 33 ms 80536 KB Output is correct
8 Correct 33 ms 80540 KB Output is correct
9 Correct 33 ms 80612 KB Output is correct
10 Correct 33 ms 80536 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 80588 KB Output is correct
2 Correct 35 ms 80560 KB Output is correct
3 Correct 33 ms 80588 KB Output is correct
4 Correct 32 ms 80632 KB Output is correct
5 Correct 33 ms 80580 KB Output is correct
6 Correct 33 ms 80576 KB Output is correct
7 Correct 33 ms 80536 KB Output is correct
8 Correct 33 ms 80540 KB Output is correct
9 Correct 33 ms 80612 KB Output is correct
10 Correct 33 ms 80536 KB Output is correct
11 Correct 296 ms 93184 KB Output is correct
12 Correct 57 ms 89368 KB Output is correct
13 Correct 544 ms 89216 KB Output is correct
14 Correct 526 ms 96300 KB Output is correct
15 Correct 208 ms 90272 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 80588 KB Output is correct
2 Correct 35 ms 80560 KB Output is correct
3 Correct 33 ms 80588 KB Output is correct
4 Correct 32 ms 80632 KB Output is correct
5 Correct 33 ms 80580 KB Output is correct
6 Correct 33 ms 80576 KB Output is correct
7 Correct 33 ms 80536 KB Output is correct
8 Correct 33 ms 80540 KB Output is correct
9 Correct 33 ms 80612 KB Output is correct
10 Correct 33 ms 80536 KB Output is correct
11 Correct 296 ms 93184 KB Output is correct
12 Correct 57 ms 89368 KB Output is correct
13 Correct 544 ms 89216 KB Output is correct
14 Correct 526 ms 96300 KB Output is correct
15 Correct 208 ms 90272 KB Output is correct
16 Runtime error 26 ms 34856 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -