Submission #645582

#	Time	Username	Problem	Language	Result	Execution time	Memory
645582		google	Robots (APIO13_robots)	C++17	30 / 100	1587 ms	69172 KiB

robots

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
const int INF = 0x3f3f3f3f;
int N,W,H;
string G[500];
int h[10][10],tmp[500][500];
int dist[10][500][500],dp[50][500][500];
pair<int,int> ma[500][500][4];
bool legal(int i, int j, int d){
	if (d == 0 && (i+1 == H || G[i+1][j] == 'x')) return 0;
	if (d == 1 && (j+1 == W || G[i][j+1] == 'x')) return 0;
	if (d == 2 && (i == 0 || G[i-1][j] == 'x')) return 0;
	if (d == 3 && (j == 0 || G[i][j-1] == 'x')) return 0;
	return 1;
}
/*
2 3 4
...
.2.
xxx
.1.
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

*/
pair<int,int> move(int i, int j, int d){
	int oi = i,oj = j,od = d;
	while (1){
		if (ma[i][j][d].first != -1) {
			return ma[oi][oj][od] = ma[i][j][d];
		}
		if (G[i][j] == 'A') {
			d++;
			if (d == 4) d = 0;
		}
		if (G[i][j] == 'C'){
			d--;
			if (d == -1) d = 3;
		}
		if (!legal(i,j,d)) return ma[oi][oj][od] = {i,j};
		if (d == 0) i++;
		if (d == 1) j++;
		if (d == 2) i--;
		if (d == 3) j--;
	}
}
void calc(int i, int j, int l){
	queue<pair<pair<int,int>,int>> q;
	q.push({{i,j},0});
	while (!q.empty()){
		auto [t,tt] = q.front();q.pop();
		if (dp[h[l][l]][t.first][t.second] < tt) continue;
		dp[h[l][l]][t.first][t.second] = tt;
		for (int ii = 0;ii<4;ii++)q.push({{ma[t.first][t.second][ii].first,ma[t.first][t.second][ii].second},tt+1});
	}
}
void calc1(int i1,int j1,int i2, int j2){
	//v1 = dp[h[i1][j1]],v2 = dp[h[i2][j2]]; 
	priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
	for (int i = 0;i<H;i++){
		for (int j = 0;j<W;j++){
			tmp[i][j] = min(INF,dp[h[i1][j1]][i][j]+dp[h[i2][j2]][i][j]);
			if (tmp[i][j] != INF) pq.push({tmp[i][j],{i,j}});
		}
	}
	while (!pq.empty()){
		auto [tt,t] = pq.top();pq.pop();
		if (tmp[t.first][t.second] < tt) continue;
		tmp[t.first][t.second] = tt;
		for (int ii = 0;ii<4;ii++)pq.push({tt+1,{ma[t.first][t.second][ii].first,ma[t.first][t.second][ii].second}});
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> W >> H;
	memset(ma,-1,sizeof(ma));
	memset(dist,INF,sizeof(dist));
	for (int i = 0;i<H;i++) cin >> G[i];
	for (int i = 0;i<H;i++){
		for (int j = 0;j<W;j++){
			move(i,j,0);
			move(i,j,1);
			move(i,j,2);
			move(i,j,3);
		}
	}
	int cnt = 1;
	for (int i = 1;i<=N;i++){
		for (int j = i;j<=N;j++){
			h[i][j] = cnt++;
		}
	}
	memset(dp,INF,sizeof(dp));
	for (int l = 1;l<=N;l++){
		for (int i = 0;i<H;i++){
			for (int j = 0;j<W;j++){
				if (G[i][j] == l+'0') calc(i,j,l);
			}
		}
	}
	for (auto &a:dp[0]) for (auto &aa:a) aa = 0;
	for (int k = 1;k<N;k++){
		for (int i = 1;i+k<=N;i++){
			calc1(i,i,i+1,i+k);
			for (int I = 0;I<H;I++){
				for (int J = 0;J<W;J++){
					dp[h[i][i+k]][I][J] = min(dp[h[i][i+k]][I][J],tmp[I][J]);
				}
			}
			if (k == 1) continue;
			calc1(i,i+k-1,i+k,i+k);
			for (int I = 0;I<H;I++){
				for (int J = 0;J<W;J++){
					dp[h[i][i+k]][I][J] = min(dp[h[i][i+k]][I][J],tmp[I][J]);
				}
			}
		}
	}
	int ans = INF;
	for (auto &a:dp[h[1][N]]) for (auto &aa:a) ans = min(ans,aa);
	cout << (ans==INF?-1:ans);
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40