Submission #1048967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048967		adiyer	Robots (APIO13_robots)	C++17	30 / 100	1526 ms	90960 KiB

robots

// #pragma optimize ("g",on)
// #pragma GCC optimize("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")

#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0);
#define bitcount(n) __builtin_popcountll(n)
#define puts(x) (x ? "YES\n" : "NO\n");
#define ent (i == n ? '\n' : ' ')
#define all(x) x.begin(), x.end()
#define md ((l + r) >> 1)
#define rv(v) ((v << 1) | 1)
#define lv(v) (v << 1)
#define rs(v) rv(v), md + 1, r
#define ls(v) lv(v), l, md
#define len(s) (int) s.size()

#define pb push_back
#define S second
#define F first

// #define int long long

using namespace std;

typedef int ll;
typedef long double ld;
typedef vector < ll > vll;
typedef pair < ll, ll > pll;
typedef vector < pair < ll, ll > > vpll;

const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 5e2 + 2;
const int K = 2e5;
const int mod = 998244353;
const ll inf = 1e9 + 10;

//mt19937 rnd(07062006);

ll k, n, m, res, cur, cnt;	
ll ans[51][N][N], seg[10][10];

pll was[N][N][4];

bool vis[N][N][4];

char a[N][N];

bool good(ll x, ll y){
	return x >= 1 && y >= 1 && x <= n && y <= m && a[x][y] != 'x';
}

pll dfs(ll x, ll y, ll di){
	pll &w = was[x][y][di];
	if(was[x][y][di].F) return w;
	if(vis[x][y][di]) return w = {-1, -1};
	vis[x][y][di] = 1;
	if(a[x][y] == 'A') di = (di + 1) % 4;
	if(a[x][y] == 'C') di = (di + 3) % 4;
	ll nx = x + dx[di], ny = y + dy[di];
	if(good(nx, ny)) return w = dfs(nx, ny, di);
	else return w = {x, y};
}

void bfs(pll s, ll id){
	queue < pll > q;
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++)
			ans[seg[id][id]][i][j] = inf;
	q.push(s), ans[seg[id][id]][s.F][s.S] = 0;
	while(len(q)){
		auto [x, y] = q.front();
		q.pop();
		// cout << x << ' ' << y << '\n';
		for(ll i = 0; i < 4; i++){
			auto [nx, ny] = was[x][y][i];
			// cout << "N: " << nx << ' ' << ny << '\n';
			if(nx == -1) continue;
			if(ans[seg[id][id]][nx][ny] != inf) continue;
			ans[seg[id][id]][nx][ny] = ans[seg[id][id]][x][y] + 1;
			q.push({nx, ny});
		}
	}
	// cout << '\n';
}

vll v;

vpll pos[N * N * 10];

ll num;

void output(){
	cin >> k >> m >> n, res = inf;
	for(ll i = 1; i <= k; i++)
		for(ll j = i; j <= k; j++)
			seg[i][j] = ++num;
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++)
			cin >> a[i][j];
	for(ll i = 1; i <= n; i++)	
		for(ll j = 1; j <= m; j++)	
			for(ll di = 0; di < 4; di++)
				dfs(i, j, di);
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++)
			if('1' <= a[i][j] && a[i][j] <= '9')
				bfs({i, j}, a[i][j] - '0');
	queue < pll > q;
	for(ll sz = 2; sz <= k; sz++){
		for(ll l = 1; l + sz - 1 <= k; l++){
			ll r = l + sz - 1;
			pair < ll, pll > mn = {inf, {inf, inf}};
			for(ll i = 1; i <= n; i++){
				for(ll j = 1; j <= m; j++){
					ans[seg[l][r]][i][j] = inf;
					for(ll id = l; id < r; id++) ans[seg[l][r]][i][j] = min(ans[seg[l][r]][i][j], ans[seg[l][id]][i][j] + ans[seg[id + 1][r]][i][j]);
					if(ans[seg[l][r]][i][j] < inf){
						v.pb(ans[seg[l][r]][i][j]);
						pos[ans[seg[l][r]][i][j]].pb({i, j});
						mn = min(mn, {ans[seg[l][r]][i][j], {i, j}});
					}
				}
			}
			if(mn.F == inf) continue;
			for(auto x : pos[mn.F]) q.push(x);
			pos[mn.F].clear();
			while(len(q)){
				auto [x, y] = q.front();
				q.pop();
				ll cst = ans[seg[l][r]][x][y];
				if(len(pos[cst + 1])){
					for(auto it : pos[cst + 1]){
						if(ans[seg[l][r]][it.F][it.S] <= cst) continue;
						q.push(it);
					}
					pos[cst + 1].clear();
				}
				for(ll di = 0; di < 4; di++){
					auto [nx, ny] = was[x][y][di];
					if(nx == -1 || ans[seg[l][r]][nx][ny] <= cst) continue;
					ans[seg[l][r]][nx][ny] = cst + 1;
					q.push({nx, ny});
				}
				
			}
			for(auto it : v) pos[it].clear();
			v.clear();
		}
	}
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++)
			res = min(res, ans[seg[1][k]][i][j]);
	if(res == inf) res = -1;
	cout << res;
}

const bool cases = 0;

signed main(){
//  file("disrupt");
    adiyer();
    int tt = 1;
    if(cases) cin >> tt;
    for(int i = 1; i <= tt; i++){
    	output();
    }
}

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