Submission #1003062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003062		vjudge1	Robots (APIO13_robots)	C++17	60 / 100	502 ms	163840 KiB

robots

/* author : Dinmukhammed ^_^ */

#include <map>
#include <set>
#include <unordered_set>
#include <list>
#include <cmath>
#include <ctime>                         																											
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
#include <complex>

#define ll long long
#define ld long double
#define all(x) (x).begin() , (x).end()
#define F first
#define S second
#define sz size()
#define turbo ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define ins insert
#define rall(x) (x).rbegin() , (x).rend()
#define int ll




// #ifdef cp_editor
// #else
// freopen(".in" , "r" , stdin);
// freopen(".out" , "w" , stdout);
// #endif


// #pragma GCC optimize("O3", "unroll-loops")
// #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")

using namespace std;


const ll inf = 1e18+3;
const int MOD = 1e9+7;
const long double eps = 1e-11;

ll rnd(){
	ll x = rand() << 15;
	return rand() ^ x;
}

ll binpow(ll a , ll b){
    if (!b) return 1;
    if (b % 2){
        return (a * binpow(a , b - 1)) % MOD;
    }
    else{
        ll val = binpow(a , b / 2);
        return (val * val) % MOD;
    }
}



const int N = 500 + 3;
const int NN = 2e6+3;
const int N1 = 2000+3;
const int lg = 22;


const int dx[] = {1 , 0 , -1 , 0};
const int dy[] = {0 , 1 , 0 , -1};


int n , m , coln;

char a[N][N];

int id = 0;

pair <int , int> used[N][N][4];

pair <int , int> find(int x , int y , int k){
	if(used[x][y][k].F) return used[x][y][k];
	used[x][y][k] = {-1 , -1};
	int k1 = k;
	if(a[x][y] == 'C') k = (k - 1 + 4) % 4;
	if(a[x][y] == 'A') k = (k + 1) % 4;
	if(a[x + dx[k]][y + dy[k]] == 'x' || (x + dx[k] < 1 || y + dy[k] < 1 || x + dx[k] > n || y + dy[k] > m)) return used[x][y][k1] = {x , y};
	return used[x][y][k1] = find(x + dx[k] , y + dy[k] , k);
}

vector <pair <int , int>> g[N][N];

void build(){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[i][j] == 'x') continue;
			for(int k = 0; k < 4; k++){
				pair <int , int> p = find(i , j , k);
				if(p.F != -1) g[i][j].pb(p);
			}
		}
	}
}

void code(){
	cin >> coln >> m >> n;
	vector <pair <int , pair <int , int>>> rbt;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			if(a[i][j] >= '1' && a[i][j] <= '9') rbt.pb({a[i][j] - '0' , {i , j}});
		}
	}
	build();
	ll dp[coln + 1][coln + 1][n + 1][m + 1];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			for(int l = 1; l <= coln; l++){
				for(int r = l; r <= coln; r++) dp[l][r][i][j] = inf;
			}
		}
	}
	for(auto [ind , cor] : rbt){
		dp[ind][ind][cor.F][cor.S] = 0;
	}
	for(int sz1 = 1; sz1 <= coln; sz1++){
		for(int l = 1; l <= coln - sz1 + 1; l++){
			int r = l + sz1 - 1;
			set <pair <int , pair <int , int>>> st;
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= m; j++){
					for(int mid = l; mid < r; mid++){
						dp[l][r][i][j] = min(dp[l][r][i][j] , dp[l][mid][i][j] + dp[mid + 1][r][i][j]);
					}
					if(dp[l][r][i][j] != inf) st.ins({dp[l][r][i][j] , {i , j}});
				}
			}
			while(!st.empty()){
				int x , y;
				tie(x , y) = st.begin() -> S;
				st.erase(st.begin());
				for(auto to : g[x][y]){
					if(dp[l][r][to.F][to.S] > dp[l][r][x][y] + 1){
						st.erase({dp[l][r][to.F][to.S] , to});
						dp[l][r][to.F][to.S] = dp[l][r][x][y] + 1;
						st.ins({dp[l][r][to.F][to.S] , to});
					}
				}
			}
		}
	}
	ll mn = inf;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			mn = min(mn , dp[1][coln][i][j]);
		}
	}
	// for(auto to : g[5][5]){
		// cout << to.F << " " << to.S << "\n";
	// }
	// cout << dp[3][4][1][7] << " ";
	if(mn == inf) cout << -1;
	else cout << mn;
}




signed main(/* oblys -> respa -> mezhdynarodka */){
	turbo
	// freopen("haircut.in" , "r" , stdin);
	// freopen("haircut.out" , "w" , stdout);
	int tt = 1;
	// cin >> tt;
	for(int _ = 1; _ <= tt; _++){
		code();
		// cout << "\n";
	}
}

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