oj.uz

Submission #500729

# Submission time Handle Problem Language Result Execution time Memory
500729 2022-01-01T00:09:54 Z super_j6 Robots (APIO13_robots) C++14
0 / 100
 64 ms 163844 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 = 500, 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 163844 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 163844 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 163844 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 163844 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -