oj.uz

Submission #1003065

# Submission time Handle Problem Language Result Execution time Memory
1003065 2024-06-20T04:55:59 Z vjudge1 Robots (APIO13_robots) C++17
60 / 100
 388 ms 163840 KB 
/* 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][6];

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 + 3][coln + 3][n + 3][m + 3];
	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6400 KB Output is correct
3 Correct 2 ms 6404 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6400 KB Output is correct
3 Correct 2 ms 6404 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6236 KB Output is correct
7 Correct 2 ms 6404 KB Output is correct
8 Correct 2 ms 6324 KB Output is correct
9 Correct 2 ms 6208 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6400 KB Output is correct
3 Correct 2 ms 6404 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6236 KB Output is correct
7 Correct 2 ms 6404 KB Output is correct
8 Correct 2 ms 6324 KB Output is correct
9 Correct 2 ms 6208 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 143 ms 115916 KB Output is correct
12 Correct 16 ms 23900 KB Output is correct
13 Correct 55 ms 86036 KB Output is correct
14 Correct 388 ms 116816 KB Output is correct
15 Correct 110 ms 115280 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 2 ms 6400 KB Output is correct
3 Correct 2 ms 6404 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6236 KB Output is correct
7 Correct 2 ms 6404 KB Output is correct
8 Correct 2 ms 6324 KB Output is correct
9 Correct 2 ms 6208 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 143 ms 115916 KB Output is correct
12 Correct 16 ms 23900 KB Output is correct
13 Correct 55 ms 86036 KB Output is correct
14 Correct 388 ms 116816 KB Output is correct
15 Correct 110 ms 115280 KB Output is correct
16 Runtime error 95 ms 163840 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -