oj.uz

답안 #1093947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1093947 2024-09-28T06:31:08 Z Trisanu_Das 로봇 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -