Submission #1275888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275888		KluydQ	Robots (APIO13_robots)	C++20	100 / 100	1116 ms	62340 KiB

robots

#include <bits/stdc++.h>

#define respagold ios_base::sync_with_stdio(0), cin.tie(0);     
//#define int short
#define ll long long
#define int2 __int128_t
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define pii pair <int, int>
#define ppi pair <pair <int, int>, int>
#define pip pair <int, pair <int, int>>
#define mkp make_pair
 
using namespace std;
 
const int N = 501;
const int inf = 1e9 + 1;
const double eps = 1e-20;

short n, m, x, y, k, use[4][N][N], tim, cntop; int dp[10][10][N][N];
char a[N][N]; pair <short, short> used[4][N][N], robot[10];
priority_queue <pair <int, pair <short, short>>> q;
vector <pair <short, short>> g[N][N];

short dx[4] = {0, -1, 0, 1};
short dy[4] = {1, 0, -1, 0};
short da[4] = {1, 2, 3, 0};
short dc[4] = {3, 0, 1, 2};

bool ok( short x, short y )
{
	if( x > n || y > m || min(x, y) < 1 || a[x][y] == 'x' ) return 0;
	return 1;
}
pair <short, short> rec( short x, short y, short tp )
{
	if( used[tp][x][y].F != 0 ) return used[tp][x][y];
	short ptp = tp; used[tp][x][y] = {-1, -1};
	
	if( a[x][y] == 'A' ) tp = da[ptp]; 
	if( a[x][y] == 'C' ) tp = dc[ptp];
	
	if( !ok(x + dx[tp], y + dy[tp]) ) return used[ptp][x][y] = {x, y};
	else return used[ptp][x][y] = rec( x + dx[tp], y + dy[tp], tp );
}
void solve()
{
	cin >> k >> m >> n;
	
	FOR( i, 1, n, 1 )
	{
		FOR( j, 1, m, 1 ) cin >> a[i][j];
	}
	FOR( i, 1, n, 1 )
	{
		FOR( j, 1, m, 1 )
		{
			if( a[i][j] == 'x' ) continue;
			
			FOR( tp, 0, 3, 1 )
			{
				pair <short, short> v = rec(i, j, tp);
				if( v.F != -1 ) g[i][j].pb(v);
			}
			if( '1' <= a[i][j] && a[i][j] <= '9' ) robot[a[i][j] - '0'] = {i, j};
		}
	}
	FOR( i, 1, n, 1 ) FOR( j, 1, m, 1 ) FOR( f, 1, k, 1 ) FOR( s, f, k, 1 ) dp[f][s][i][j] = inf; 
	FOR( i, 1, k, 1 ) dp[i][i][robot[i].F][robot[i].S] = 0;
	
	FOR( len, 1, k, 1 )
	{
		FOR( l, 1, k - len + 1, 1 )
		{
			int r = len + l - 1;
			
			FOR( i, 1, n, 1 )
			{
				FOR( j, 1, m, 1 )
				{
					FOR( md, l, r - 1, 1 ) dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][md][i][j] + dp[md + 1][r][i][j]);
				}
			}
			if( len == k ) continue;
			
			FOR( i, 1, n, 1 )
			{
				FOR( j, 1, m, 1 )
				{
					if( dp[l][r][i][j] != inf ) q.push({-dp[l][r][i][j], {i, j}});
				}
			}
			while( !q.empty() )
			{
				pip p = q.top();
				q.pop(); pii v = p.S;
				if( p.F > dp[l][r][v.F][v.S] ) continue;
				
				for( auto to : g[v.F][v.S] )
				{
					if( dp[l][r][to.F][to.S] > dp[l][r][v.F][v.S] + 1 )
					{
						dp[l][r][to.F][to.S] = dp[l][r][v.F][v.S] + 1;
						q.push({-dp[l][r][to.F][to.S], {to.F, to.S}});
					}
				}
			}
		}
	}
	int ans = inf;
	
	FOR( i, 1, n, 1 )
	{
		FOR( j, 1, m, 1 )
		{
			ans = min(ans, dp[1][k][i][j]);
		}
	}
	cout << (ans == inf ? -1 : ans);	
}
signed main()
{
	respagold
	
	int test = 1;
	if( !test ) cin >> test;
	while( test -- ) solve();
}

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