oj.uz

Submission #500716

# Submission time Handle Problem Language Result Execution time Memory
500716 2021-12-31T21:40:01 Z super_j6 Robots (APIO13_robots) C++14
60 / 100
 527 ms 147048 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], dp[mxk][mxk][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];
	}
	
	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[x][x][u] = 0;
		}
	}
	
	for(int i = k - 1; ~i; i--)
	for(int j = i; j < k; 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[i][j][l] = min(dp[i][j][l], dp[i][p][l] + dp[p + 1][j][l]);
			}
			if(dp[i][j][l] < z) q[dp[i][j][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[i][j][p] > x) q[dp[i][j][p] = x].push_back(p);
			}
		}
	}
	
	int ret = *min_element(dp[0][k - 1], dp[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 48 ms 131296 KB Output is correct
2 Correct 51 ms 131284 KB Output is correct
3 Correct 51 ms 131252 KB Output is correct
4 Correct 49 ms 131288 KB Output is correct
5 Correct 54 ms 131268 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 131296 KB Output is correct
2 Correct 51 ms 131284 KB Output is correct
3 Correct 51 ms 131252 KB Output is correct
4 Correct 49 ms 131288 KB Output is correct
5 Correct 54 ms 131268 KB Output is correct
6 Correct 51 ms 131336 KB Output is correct
7 Correct 48 ms 131344 KB Output is correct
8 Correct 48 ms 131340 KB Output is correct
9 Correct 47 ms 131268 KB Output is correct
10 Correct 50 ms 131244 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 131296 KB Output is correct
2 Correct 51 ms 131284 KB Output is correct
3 Correct 51 ms 131252 KB Output is correct
4 Correct 49 ms 131288 KB Output is correct
5 Correct 54 ms 131268 KB Output is correct
6 Correct 51 ms 131336 KB Output is correct
7 Correct 48 ms 131344 KB Output is correct
8 Correct 48 ms 131340 KB Output is correct
9 Correct 47 ms 131268 KB Output is correct
10 Correct 50 ms 131244 KB Output is correct
11 Correct 277 ms 143888 KB Output is correct
12 Correct 72 ms 140100 KB Output is correct
13 Correct 527 ms 139956 KB Output is correct
14 Correct 433 ms 147048 KB Output is correct
15 Correct 206 ms 140996 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 131296 KB Output is correct
2 Correct 51 ms 131284 KB Output is correct
3 Correct 51 ms 131252 KB Output is correct
4 Correct 49 ms 131288 KB Output is correct
5 Correct 54 ms 131268 KB Output is correct
6 Correct 51 ms 131336 KB Output is correct
7 Correct 48 ms 131344 KB Output is correct
8 Correct 48 ms 131340 KB Output is correct
9 Correct 47 ms 131268 KB Output is correct
10 Correct 50 ms 131244 KB Output is correct
11 Correct 277 ms 143888 KB Output is correct
12 Correct 72 ms 140100 KB Output is correct
13 Correct 527 ms 139956 KB Output is correct
14 Correct 433 ms 147048 KB Output is correct
15 Correct 206 ms 140996 KB Output is correct
16 Runtime error 28 ms 34944 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -