oj.uz

Submission #552413

# Submission time Handle Problem Language Result Execution time Memory
552413 2022-04-23T06:23:08 Z QwertyPi Robots (APIO13_robots) C++14
60 / 100
 927 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 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;
			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 6100 KB Output is correct
2 Correct 3 ms 6356 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 4 ms 6228 KB Output is correct
5 Correct 3 ms 6228 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 6356 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 4 ms 6228 KB Output is correct
5 Correct 3 ms 6228 KB Output is correct
6 Correct 3 ms 6228 KB Output is correct
7 Correct 3 ms 6228 KB Output is correct
8 Correct 3 ms 6160 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6348 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 6356 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 4 ms 6228 KB Output is correct
5 Correct 3 ms 6228 KB Output is correct
6 Correct 3 ms 6228 KB Output is correct
7 Correct 3 ms 6228 KB Output is correct
8 Correct 3 ms 6160 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6348 KB Output is correct
11 Correct 125 ms 47916 KB Output is correct
12 Correct 31 ms 40556 KB Output is correct
13 Correct 43 ms 40788 KB Output is correct
14 Correct 364 ms 66912 KB Output is correct
15 Correct 80 ms 43128 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6100 KB Output is correct
2 Correct 3 ms 6356 KB Output is correct
3 Correct 3 ms 6100 KB Output is correct
4 Correct 4 ms 6228 KB Output is correct
5 Correct 3 ms 6228 KB Output is correct
6 Correct 3 ms 6228 KB Output is correct
7 Correct 3 ms 6228 KB Output is correct
8 Correct 3 ms 6160 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6348 KB Output is correct
11 Correct 125 ms 47916 KB Output is correct
12 Correct 31 ms 40556 KB Output is correct
13 Correct 43 ms 40788 KB Output is correct
14 Correct 364 ms 66912 KB Output is correct
15 Correct 80 ms 43128 KB Output is correct
16 Correct 130 ms 95028 KB Output is correct
17 Runtime error 927 ms 163840 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -