Submission #389550

#	Time	Username	Problem	Language	Result	Execution time	Memory
389550		jjang36524	Robots (APIO13_robots)	C++14	100 / 100	803 ms	98312 KiB

robots

#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
#define itn int
pair<short, short>lastp[501][501][4];
int dp[45][501][501];
char arr[501][501];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int N, M, K;
int isv(int n, int m)
{
	return (n < 0) || (n >= N) || (m < 0) || (m >= M) || (arr[n][m] == 'x');
}
int ge(int n, int m)
{
	int ans = m - n;
	int i;
	for (i = 0; i < n; i++)
		ans += K - i;
	return ans;
}
pair<int, int> findne(int n, int m, int c)
{
	if (lastp[n][m][c].first != -1)
		return lastp[n][m][c];
	lastp[n][m][c] = { -2,-2 };
	if (isv(n, m))
	{
		return lastp[n][m][c];
	}
	int on = n;
	int om = m;
	int oc = c;
	if (arr[n][m] == 'A')
		c--;
	if (arr[n][m] == 'C')
		c++;
	c += 4;
	c %= 4;
	n += dx[c];
	m += dy[c];
	if (isv(n, m))
	{
		return lastp[on][om][oc] = { on,om };
	}
	return lastp[on][om][oc] = findne(n, m, c);
}
vector<pair<short, short>>co[300100];
int vis[501][501];
int main()
{
	memset(lastp, -1, sizeof(lastp));
	memset(dp, 1, sizeof(dp));
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> K >> M >> N;
	int i, j, k, l, m;
	for (i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (arr[i][j] >= '0' && arr[i][j] <= '9')
			{
				dp[ge(arr[i][j] - '1', arr[i][j] - '1')][i][j] = 0;
			}
			for (k = 0; k < 4; k++)
				findne(i, j, k);
		}
	}
	int ans = 123456789;
	for (i = 0; i < K; i++)
	{
		int j;
		for (j = 0; j < K - i; j++)
		{
			memset(vis, 0, sizeof(vis));
			int s = j;
			int e = j + i;
			for (k = 0; k <= N * M; k++)
			{
				co[k].clear();
			}
			for (k = s; k < e; k++)
			{
				for (l = 0; l < N; l++)
				{
					for (m = 0; m < M; m++)
					{
						dp[ge(s, e)][l][m] = min((int)dp[ge(s, e)][l][m], dp[ge(s, k)][l][m] + dp[ge(k + 1, e)][l][m]);
						if (i == K - 1)
							ans = min(ans, (int)dp[ge(s, e)][l][m]);
					}
				}
			}
			for (l = 0; l < N; l++)
			{
				for (m = 0; m < M; m++)
				{
					if (dp[ge(s, e)][l][m] <= N * M)
						co[dp[ge(s, e)][l][m]].push_back({ l,m });
				}
			}
			for (k = 0; k <= N * M; k++)
			{
				int l;
				for (l = 0; l < co[k].size(); l++)
				{
					if (co[k][l].first < 0 || vis[co[k][l].first][co[k][l].second])
						continue;
					dp[ge(s, e)][co[k][l].first][co[k][l].second] = k;
					if (i == K - 1)
						ans = min(ans, k);
					vis[co[k][l].first][co[k][l].second] = 1;
					for (m = 0; m < 4; m++)
					{
						co[k + 1].push_back(lastp[co[k][l].first][co[k][l].second][m]);
					}
				}
			}
		}
	}
	if (ans > N * M)
		cout << -1;
	else
		cout << ans;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<short int, short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (l = 0; l < co[k].size(); l++)
      |                 ~~^~~~~~~~~~~~~~

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