oj.uz

Submission #552417

# Submission time Handle Problem Language Result Execution time Memory
552417 2022-04-23T06:40:19 Z QwertyPi Robots (APIO13_robots) C++14
100 / 100
 927 ms 143652 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 x = 0; x < n; x++){
			for(int y = 0; y < m; y++){
				for(int dl = 0; dl < i - 1; dl++){
					for(int dm = dl; dm < i - 1; dm++){
						dp[x][y][dl][i] = min(dp[x][y][dl][i], dp[x][y][dl][dm] + dp[x][y][dm + 1][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;
			dp[pos[i].fi][pos[i].se][j - 1][i] = c;
		}
		dp[pos[i].fi][pos[i].se][i][i] = 0;
		for(int q0 = i; q0 >= 0; q0--){
			for(int x = 0; x < n; x++) for(int y = 0; y < m; y++) if(dp[x][y][q0][i] < INF) q[dp[x][y][q0][i]].push_back({q0, {x, y}});
			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];
						}
					}
				}
			}
		}
	}
	
	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 6100 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 5 ms 6356 KB Output is correct
5 Correct 4 ms 6356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 5 ms 6356 KB Output is correct
5 Correct 4 ms 6356 KB Output is correct
6 Correct 3 ms 6276 KB Output is correct
7 Correct 3 ms 6228 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 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 6100 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 5 ms 6356 KB Output is correct
5 Correct 4 ms 6356 KB Output is correct
6 Correct 3 ms 6276 KB Output is correct
7 Correct 3 ms 6228 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6356 KB Output is correct
11 Correct 146 ms 45200 KB Output is correct
12 Correct 28 ms 40584 KB Output is correct
13 Correct 61 ms 40652 KB Output is correct
14 Correct 290 ms 53836 KB Output is correct
15 Correct 116 ms 41656 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 5 ms 6356 KB Output is correct
5 Correct 4 ms 6356 KB Output is correct
6 Correct 3 ms 6276 KB Output is correct
7 Correct 3 ms 6228 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6356 KB Output is correct
11 Correct 146 ms 45200 KB Output is correct
12 Correct 28 ms 40584 KB Output is correct
13 Correct 61 ms 40652 KB Output is correct
14 Correct 290 ms 53836 KB Output is correct
15 Correct 116 ms 41656 KB Output is correct
16 Correct 220 ms 95072 KB Output is correct
17 Correct 927 ms 143652 KB Output is correct
18 Correct 307 ms 100020 KB Output is correct
19 Correct 219 ms 95180 KB Output is correct
20 Correct 704 ms 116180 KB Output is correct