oj.uz

Submission #1003082

# Submission time Handle Problem Language Result Execution time Memory
1003082 2024-06-20T05:24:50 Z vjudge1 Robots (APIO13_robots) C++17
100 / 100
 1226 ms 127024 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 = 1e9;
// 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];
 
 
pair <int , int> used[N][N][5];
 
pair <int , int> find(int x , int y , int k){
	if(used[x][y][k].F > 0) 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();
	int dp[10][10][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 = 1; 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});
					}
				}
			}
		}
	}
	int 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 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6232 KB Output is correct
4 Correct 2 ms 6408 KB Output is correct
5 Correct 2 ms 6368 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6232 KB Output is correct
4 Correct 2 ms 6408 KB Output is correct
5 Correct 2 ms 6368 KB Output is correct
6 Correct 2 ms 6236 KB Output is correct
7 Correct 2 ms 6236 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 3 ms 6232 KB Output is correct
10 Correct 3 ms 6488 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6232 KB Output is correct
4 Correct 2 ms 6408 KB Output is correct
5 Correct 2 ms 6368 KB Output is correct
6 Correct 2 ms 6236 KB Output is correct
7 Correct 2 ms 6236 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 3 ms 6232 KB Output is correct
10 Correct 3 ms 6488 KB Output is correct
11 Correct 120 ms 49076 KB Output is correct
12 Correct 24 ms 47452 KB Output is correct
13 Correct 39 ms 49392 KB Output is correct
14 Correct 382 ms 50004 KB Output is correct
15 Correct 75 ms 48212 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6232 KB Output is correct
4 Correct 2 ms 6408 KB Output is correct
5 Correct 2 ms 6368 KB Output is correct
6 Correct 2 ms 6236 KB Output is correct
7 Correct 2 ms 6236 KB Output is correct
8 Correct 2 ms 6236 KB Output is correct
9 Correct 3 ms 6232 KB Output is correct
10 Correct 3 ms 6488 KB Output is correct
11 Correct 120 ms 49076 KB Output is correct
12 Correct 24 ms 47452 KB Output is correct
13 Correct 39 ms 49392 KB Output is correct
14 Correct 382 ms 50004 KB Output is correct
15 Correct 75 ms 48212 KB Output is correct
16 Correct 134 ms 127024 KB Output is correct
17 Correct 1226 ms 126032 KB Output is correct
18 Correct 229 ms 122280 KB Output is correct
19 Correct 137 ms 121548 KB Output is correct
20 Correct 747 ms 123500 KB Output is correct