oj.uz

Submission #541310

# Submission time Handle Problem Language Result Execution time Memory
541310 2022-03-23T02:11:01 Z jiahng Robots (APIO13_robots) C++14
100 / 100
 367 ms 91232 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ll int
//~ #define int ll
typedef pair<ll, ll> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxh 501
#define maxn 10
#define INF 1e9
#define MOD 998244353
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;

int N,H,W;
char A[maxh][maxh];
pi dp[maxh][maxh][4];
int dr[] = {-1,0,1,0}; //clockwise from up
int dc[] = {0,1,0,-1};
int dp2[maxn][maxn][maxh][maxh];
vector <pi> Q[maxh*maxh+10];

pi dfs(int i,int j,int k){
	//~ cout << i << ' ' << j << ' ' << k << '\n';
	if (dp[i][j][k] == pi(0,0)){
		//~ assert(0);
		return dp[i][j][k] = pi(-1,-2);
	}
	if (dp[i][j][k] != pi(-1,-1)) return dp[i][j][k];
	
	dp[i][j][k] = pi(0,0);
	int nk = k;
	if (A[i][j] == 'A') (nk+=3) %= 4;
	if (A[i][j] == 'C') (nk+=1) %= 4;
	
	int nr = i + dr[nk];
	int nc = j + dc[nk];
	
	if (nr < 1 || nr > H || nc < 1 || nc > W || A[nr][nc] == 'x') dp[i][j][k] = pi(i,j);
	else dp[i][j][k] = dfs(nr, nc, nk);
	return dp[i][j][k];
}



int32_t main(){
    fast;
    
    cin >> N >> W >> H;
    FOR(i,1,H) FOR(j,1,W) cin >> A[i][j];
    
    // find where each (i,j,k) goes to
    FOR(i,1,H) FOR(j,1,W) FOR(k,0,3) dp[i][j][k] = pi(-1,-1);
    FOR(i,1,H) FOR(j,1,W) FOR(k,0,3) if (dp[i][j][k] == pi(-1,-1)) dfs(i,j,k);
	//~ cout << dp[1][1][2].f << ' ' << dp[1][1][2].s;
	//~ return 0;
	FOR(l,1,N) FOR(a,1,N){ 
		int b = a + l - 1; if (b > N) continue;
		FOR(x,1,H) FOR(y,1,W){
			dp2[a][b][x][y] = INF;
			FOR(c, a, b-1) dp2[a][b][x][y] = min(
				dp2[a][b][x][y], dp2[a][c][x][y] + dp2[c+1][b][x][y]);
				
			if (a == b && A[x][y] == a + '0') dp2[a][b][x][y] = 0;
		}
		
		FOR(x,1,H) FOR(y,1,W) if (dp2[a][b][x][y] <= H * W) Q[dp2[a][b][x][y]].pb(pi(x,y));
		//~ FOR(x,1,H) FOR(y,1,W) dist[x][y] = -1;
		FOR(d,0,H*W){
			while (!Q[d].empty()){
				pi cur = Q[d].back(); Q[d].pop_back();
				if (dp2[a][b][cur.f][cur.s] != d) continue;
				FOR(k,0,3) if (dp[cur.f][cur.s][k].f != -1){
					pi x = dp[cur.f][cur.s][k];
					if (dp2[a][b][x.f][x.s] > d + 1){
						dp2[a][b][x.f][x.s] = d + 1;
						Q[d+1].pb(x);
					}
				}
			}
		}
		
	}
	//~ aFOR(i,adj[5][5]) cout << i.f << ' ' << i.s << '\n';
	//~ return 0;
	//~ cout << dp2[2][2][5][5];
	//~ return 0;
	int ans = INF;
	FOR(i,1,H) FOR(j,1,W) ans = min(ans, dp2[1][N][i][j]);
	cout << (ans == INF ? -1 : ans);
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 4 ms 6248 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 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 6228 KB Output is correct
2 Correct 4 ms 6248 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 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 6184 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6228 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 4 ms 6248 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 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 6184 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6228 KB Output is correct
11 Correct 65 ms 40688 KB Output is correct
12 Correct 12 ms 11476 KB Output is correct
13 Correct 31 ms 27112 KB Output is correct
14 Correct 125 ms 45904 KB Output is correct
15 Correct 56 ms 38012 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 4 ms 6248 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 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 6184 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6228 KB Output is correct
11 Correct 65 ms 40688 KB Output is correct
12 Correct 12 ms 11476 KB Output is correct
13 Correct 31 ms 27112 KB Output is correct
14 Correct 125 ms 45904 KB Output is correct
15 Correct 56 ms 38012 KB Output is correct
16 Correct 116 ms 58776 KB Output is correct
17 Correct 367 ms 91232 KB Output is correct
18 Correct 126 ms 62980 KB Output is correct
19 Correct 105 ms 58904 KB Output is correct
20 Correct 204 ms 73780 KB Output is correct