oj.uz

Submission #389550

# Submission time Handle Problem Language Result Execution time Memory
389550 2021-04-14T07:19:05 Z jjang36524 Robots (APIO13_robots) C++14
100 / 100
 803 ms 98312 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56344 KB Output is correct
2 Correct 29 ms 56444 KB Output is correct
3 Correct 35 ms 56400 KB Output is correct
4 Correct 31 ms 56492 KB Output is correct
5 Correct 30 ms 56396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56344 KB Output is correct
2 Correct 29 ms 56444 KB Output is correct
3 Correct 35 ms 56400 KB Output is correct
4 Correct 31 ms 56492 KB Output is correct
5 Correct 30 ms 56396 KB Output is correct
6 Correct 30 ms 56388 KB Output is correct
7 Correct 30 ms 56360 KB Output is correct
8 Correct 30 ms 56480 KB Output is correct
9 Correct 29 ms 56416 KB Output is correct
10 Correct 29 ms 56396 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56344 KB Output is correct
2 Correct 29 ms 56444 KB Output is correct
3 Correct 35 ms 56400 KB Output is correct
4 Correct 31 ms 56492 KB Output is correct
5 Correct 30 ms 56396 KB Output is correct
6 Correct 30 ms 56388 KB Output is correct
7 Correct 30 ms 56360 KB Output is correct
8 Correct 30 ms 56480 KB Output is correct
9 Correct 29 ms 56416 KB Output is correct
10 Correct 29 ms 56396 KB Output is correct
11 Correct 232 ms 64852 KB Output is correct
12 Correct 39 ms 57420 KB Output is correct
13 Correct 104 ms 56780 KB Output is correct
14 Correct 321 ms 69320 KB Output is correct
15 Correct 193 ms 58808 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56344 KB Output is correct
2 Correct 29 ms 56444 KB Output is correct
3 Correct 35 ms 56400 KB Output is correct
4 Correct 31 ms 56492 KB Output is correct
5 Correct 30 ms 56396 KB Output is correct
6 Correct 30 ms 56388 KB Output is correct
7 Correct 30 ms 56360 KB Output is correct
8 Correct 30 ms 56480 KB Output is correct
9 Correct 29 ms 56416 KB Output is correct
10 Correct 29 ms 56396 KB Output is correct
11 Correct 232 ms 64852 KB Output is correct
12 Correct 39 ms 57420 KB Output is correct
13 Correct 104 ms 56780 KB Output is correct
14 Correct 321 ms 69320 KB Output is correct
15 Correct 193 ms 58808 KB Output is correct
16 Correct 482 ms 56992 KB Output is correct
17 Correct 803 ms 98312 KB Output is correct
18 Correct 483 ms 63772 KB Output is correct
19 Correct 447 ms 57128 KB Output is correct
20 Correct 637 ms 85676 KB Output is correct