oj.uz

Submission #552407

# Submission time Handle Problem Language Result Execution time Memory
552407 2022-04-23T06:12:30 Z QwertyPi Robots (APIO13_robots) C++14
60 / 100
 924 ms 163840 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 501, MAXM = 501, MAXD = 9;
const int INF = (1 << 25);
char board[MAXN][MAXM];
int dp[MAXN][MAXM][MAXD][MAXD];
int dd[MAXN][MAXM];
pii f[MAXN][MAXM][4];
pii pos[MAXD];
 
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
 
int d, n, m;
bool in(int i, int j){
	return 0 <= i && i < n && 0 <= j && j < m && board[i][j] != 'x';
}
 
bool vis[MAXN][MAXM][4];
inline pii dfs(int i, int j, int dir){
	if(vis[i][j][dir]) return {-1, -1};
	if(f[i][j][dir].fi != -2) return f[i][j][dir];
	vis[i][j][dir] = true;
	if(!in(i + dx[dir], j + dy[dir])){
		f[i][j][dir] = {i, j};
		vis[i][j][dir] = false;
		return {i, j};
	}
	f[i][j][dir] = dfs(i + dx[dir], j + dy[dir], (dir + dd[i + dx[dir]][j + dy[dir]] + 4) % 4);
	vis[i][j][dir] = false;
	return f[i][j][dir];
}
 
struct CMP{
	bool operator()(pair<pii, pii> a, pair<pii, pii> b){
		return a.fi.fi > b.fi.fi;
	}
};
 
vector<pair<int, pii>> q[MAXN * MAXM];
int main(){
	cin >> d >> m >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> board[i][j];
			if(board[i][j] >= '0' && board[i][j] <= '9') pos[board[i][j] - '1'] = {i, j}, board[i][j] = '.';
			if(board[i][j] == 'C') dd[i][j] = 1;
			if(board[i][j] == 'A') dd[i][j] = -1;
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int dir = 0; dir < 4; dir++){
				f[i][j][dir].fi = -2;
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int dir = 0; dir < 4; dir++){
				if(f[i][j][dir].fi == -2) dfs(i, j, dir);
			}
		}
	}
//	for(int i = 0; i < n; i++){
//		for(int j = 0; j < m; j++){
//			for(int k = 0; k < 4; k++){
//				cout << i << ' ' << j << ' ' << k << ' ' << f[i][j][k].fi << ' ' << f[i][j][k].se << endl;
//			}
//		}
//	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int d1 = 0; d1 < d; d1++){
				for(int d2 = d1; d2 < d; d2++){
					dp[i][j][d1][d2] = INF;
				}
			}
		}
	}

	for(int i = 0; i < d; i++){
		for(int j = i; j >= 1; j--){
			int c = dp[pos[i].fi][pos[i].se][j - 1][i - 1];
			if(c >= INF) continue;
			q[c].push_back({j - 1, pos[i]});
			dp[pos[i].fi][pos[i].se][j - 1][i] = c;
		}
		q[0].push_back({i, pos[i]});
		dp[pos[i].fi][pos[i].se][i][i] = 0;
		for(int k = 0; k <= n * m; k++){
			while(!q[k].empty()){
				pair<int, pii> v = q[k].back(); q[k].pop_back();
				int nd = v.fi, x = v.se.fi, y = v.se.se;
				for(int dir = 0; dir < 4; dir++){
					int nx = f[x][y][dir].fi, ny = f[x][y][dir].se;
					if(nx == x && ny == y) continue;
					int co = k + 1;
					if(co >= dp[nx][ny][nd][i]) continue;
					dp[nx][ny][nd][i] = co;
					q[co].push_back({nd, {nx, ny}});
					for(int j = nd; j >= 1; j--){
						if(co + dp[nx][ny][j - 1][nd - 1] >= dp[nx][ny][j - 1][i]) continue;
						dp[nx][ny][j - 1][i] = co + dp[nx][ny][j - 1][nd - 1];
						q[co + dp[nx][ny][j - 1][nd - 1]].push_back({j - 1, {nx, ny}});
					}
				}
			}
		}
	}
	
	int ans = INF;
//	for(int d1 = 0; d1 < d; d1++){
//		for(int d2 = d1; d2 < d; d2++){
//			cout << "d " << d1 << ' ' << d2 << endl;
//			for(int i = 0; i < n; i++){
//				for(int j = 0; j < m; j++){
//					cout << (dp[i][j][d1][d2] >= INF ? -1 : dp[i][j][d1][d2]) << ' ';
//				}
//				cout << endl;
//			}
//		}
//	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			ans = min(ans, dp[i][j][0][d - 1]);
		}
	}
	cout << (ans >= INF ? -1 : ans) << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 3 ms 6100 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 4 ms 6228 KB Output is correct
10 Correct 3 ms 6356 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 3 ms 6100 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 4 ms 6228 KB Output is correct
10 Correct 3 ms 6356 KB Output is correct
11 Correct 109 ms 47880 KB Output is correct
12 Correct 30 ms 40624 KB Output is correct
13 Correct 32 ms 40724 KB Output is correct
14 Correct 393 ms 66748 KB Output is correct
15 Correct 68 ms 43100 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 3 ms 6100 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 4 ms 6228 KB Output is correct
10 Correct 3 ms 6356 KB Output is correct
11 Correct 109 ms 47880 KB Output is correct
12 Correct 30 ms 40624 KB Output is correct
13 Correct 32 ms 40724 KB Output is correct
14 Correct 393 ms 66748 KB Output is correct
15 Correct 68 ms 43100 KB Output is correct
16 Correct 89 ms 94988 KB Output is correct
17 Runtime error 924 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -