Submission #1002444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002444		vjudge1	Robots (APIO13_robots)	C++17	100 / 100	1403 ms	82744 KiB

robots

#include <bits/stdc++.h>

using namespace std;
using ll  =  long long;

#ifdef U_U
#include "algo/debug.h"
#else
#define deb(x...) 42
#endif
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define szof(x) (int)x.size()
//#define int ll
#define love bool

template<class T> void MIN(T& a, const T b) { b < a ? a = b, 1 : 0; }
template<class T> void MAX(T& a, const T b) { a < b ? a = b, 1 : 0; }

const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int inf = 1e9;
//2147483647;
const int INF = 9223372036854775807;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};
// Follow the white rabbit.

int n, m, nn;
char e[505][505];
int dist[505][505][10];
vector <pair <int, int> > g[505][505];
vector <pair <int, int> > v(11);
pair <int, int> was[505][505][10];
bool can (int x, int y) {
	if (x > n || x < 1 || y > m || y < 1 || e[x][y] == 'x') return 0;
	return 1;
}
pair <int, int> get (int x, int y, int k) {
	if (was[x][y][k].first) return was[x][y][k];
	was[x][y][k] = {-1, -1};
	int tmp = k;
	if (e[x][y] == 'A') k += 3, k %= 4;
	if (e[x][y] == 'C') k ++, k %= 4;
	int X = dx[k] + x, Y = dy[k] + y;
	if (can(X, Y)) {
		return was[x][y][tmp] = get(X, Y, k);
	}
	return was[x][y][tmp] = {x, y};
}
int dp[10][10][505][505];
void ka () {
	cin >> nn >> m >> n;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			cin >> e[i][j];
			if (e[i][j] >= '1' && e[i][j] <= '9') v[e[i][j] - '0'] = {i, j};
		}
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			if (!can(i, j)) continue;
			for (int k = 0; k < 4; k ++) {
				pair <int, int> tmp = get(i, j, k);
				if (tmp.first != -1) g[i][j].pb(tmp);
			}		
		}
	}
	for (int l = 1; l <= nn; l ++) {
		for (int r = l; r <= nn; r ++) {
			for (int i = 1; i <= n; i ++) {
				for (int j = 1; j <= m; j ++) {
					dp[l][r][i][j] = inf;
				}
			}
		}
	}
	for (int i = 1; i <= nn; i ++) {
		dp[i][i][v[i].first][v[i].second] = 0;
	}
	for (int len = 1; len <= nn; len ++) {
		for (int l = 1; l <= nn; l ++) {
			int r = l + len - 1;
			if (r > nn) break;
			for (int i = 1; i <= n; i ++) {
				for (int j = 1; j <= m; j ++) {				
					for (int md = l; md < r; md ++) {
						MIN(dp[l][r][i][j], dp[l][md][i][j] + dp[md + 1][r][i][j]);
					}
				}
			}
			set <pair <int, pair <int, int> > > q;
			for (int i = 1; i <= n; i ++) {
				for (int j = 1; j <= m; j ++) {
					if (dp[l][r][i][j] != inf) q.insert({dp[l][r][i][j], {i, j}});
				}
			}
			while (szof(q)) {
				pair <int, pair <int, int> > tmp = *q.begin();
				q.erase(tmp);
				for (pair <int, int> c : g[tmp.second.first][tmp.second.second]) {
					if (dp[l][r][c.first][c.second] > dp[l][r][tmp.second.first][tmp.second.second] + 1) {
						q.erase({dp[l][r][c.first][c.second], c});
						dp[l][r][c.first][c.second] = dp[l][r][tmp.second.first][tmp.second.second] + 1;
						q.insert({dp[l][r][c.first][c.second], c});
					}
				}
			}
		}
	}
	int ans = inf;
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) MIN(ans, dp[1][nn][i][j]);
	cout << (ans == inf ? -1 : ans);
}

const bool overflow = 0;

main() {
  //freopen("haircut.in"	, "r", stdin); freopen("haircut.out", "w", stdout);
  cout.setf(ios::fixed);cout.precision(12);
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int tc = 1; 
  if (overflow) cin >> tc;
  for (int cs = 1; cs <= tc; cs ++) {
		#ifdef U_U
		cout << ":D\n";
		#endif
		ka();
		//if (cs != tc) cout << '\n';
  }
}

Compilation message (stderr)

robots.cpp:25:17: warning: overflow in conversion from 'long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   25 | const int INF = 9223372036854775807;
      |                 ^~~~~~~~~~~~~~~~~~~
robots.cpp:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  119 | main() {
      | ^~~~

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