oj.uz

Submission #1093947

# Submission time Handle Problem Language Result Execution time Memory
1093947 2024-09-28T06:31:08 Z Trisanu_Das Robots (APIO13_robots) C++17
60 / 100
 313 ms 147080 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
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) << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 131412 KB Output is correct
2 Correct 63 ms 131408 KB Output is correct
3 Correct 60 ms 131492 KB Output is correct
4 Correct 64 ms 131408 KB Output is correct
5 Correct 72 ms 131492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 131412 KB Output is correct
2 Correct 63 ms 131408 KB Output is correct
3 Correct 60 ms 131492 KB Output is correct
4 Correct 64 ms 131408 KB Output is correct
5 Correct 72 ms 131492 KB Output is correct
6 Correct 62 ms 131408 KB Output is correct
7 Correct 63 ms 131284 KB Output is correct
8 Correct 62 ms 131240 KB Output is correct
9 Correct 62 ms 131408 KB Output is correct
10 Correct 70 ms 131412 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 131412 KB Output is correct
2 Correct 63 ms 131408 KB Output is correct
3 Correct 60 ms 131492 KB Output is correct
4 Correct 64 ms 131408 KB Output is correct
5 Correct 72 ms 131492 KB Output is correct
6 Correct 62 ms 131408 KB Output is correct
7 Correct 63 ms 131284 KB Output is correct
8 Correct 62 ms 131240 KB Output is correct
9 Correct 62 ms 131408 KB Output is correct
10 Correct 70 ms 131412 KB Output is correct
11 Correct 203 ms 143956 KB Output is correct
12 Correct 91 ms 140116 KB Output is correct
13 Correct 175 ms 140116 KB Output is correct
14 Correct 313 ms 147080 KB Output is correct
15 Correct 156 ms 141228 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 131412 KB Output is correct
2 Correct 63 ms 131408 KB Output is correct
3 Correct 60 ms 131492 KB Output is correct
4 Correct 64 ms 131408 KB Output is correct
5 Correct 72 ms 131492 KB Output is correct
6 Correct 62 ms 131408 KB Output is correct
7 Correct 63 ms 131284 KB Output is correct
8 Correct 62 ms 131240 KB Output is correct
9 Correct 62 ms 131408 KB Output is correct
10 Correct 70 ms 131412 KB Output is correct
11 Correct 203 ms 143956 KB Output is correct
12 Correct 91 ms 140116 KB Output is correct
13 Correct 175 ms 140116 KB Output is correct
14 Correct 313 ms 147080 KB Output is correct
15 Correct 156 ms 141228 KB Output is correct
16 Runtime error 24 ms 35304 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -