Submission #872781

#	Time	Username	Problem	Language	Result	Execution time	Memory
872781		scrge	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	105 ms	387412 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

const int maxn = 410;
const int inf = 1e9+10;

int n;
int a[maxn];

int qtd[3], pos[3][maxn];
int pref[3][maxn];

int dp[3][maxn][maxn][maxn];

int main(void)
{
	scanf("%d", &n);

	string s;
	cin >> s;

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'R')
		{
			a[i+1] = 0, ++qtd[0];
			pos[0][qtd[0]] = i+1;
		}
		else if (s[i] == 'G')
		{
			a[i+1] = 1, ++qtd[1];
			pos[1][qtd[1]] = i+1;
		}
		else
		{
			a[i+1] = 2, ++qtd[2];
			pos[2][qtd[2]] = i+1;
		}
	}

	for (int t = 0; t < 3; t++)
	{
		for (int i = 1; i <= n; i++)
		{
			pref[t][i] = pref[t][i-1];

			if (a[i] == t) ++pref[t][i];
		}
	}

	for (int i = 0; i < 3; i++)
		for (int r = 0; r <= qtd[0]; r++)
			for (int g = 0; g <= qtd[1]; g++)
				for (int y = 0; y <= qtd[2]; y++)
					dp[i][r][g][y] = inf;

	dp[0][0][0][0] = 0;
	dp[1][0][0][0] = 0;
	dp[2][0][0][0] = 0;

	for (int r = 0; r <= qtd[0]; r++)
	{
		for (int g = 0; g <= qtd[1]; g++)
		{
			for (int y = 0; y <= qtd[2]; y++)
			{
				for (int pre = 0; pre < 3; pre++)
				{
					for (int at = 0; at < 3; at++)
					{
						if (at == pre) continue;
						if ((at == 0 && r == qtd[0]) || (at == 1 && g == qtd[1]) || (at == 2 && y == qtd[2])) continue;

						int ans = 0;

						// pos. of color 'pre', pos. of color 'at' and pos. of other color 'dif'
						int p1, p2, p3, dif;

						// These ifs are used only to find the correct values for p1, p2 and p3
						if (pre == 0)
						{
							p1 = pos[0][r];

							if (at == 1) p2 = pos[1][g+1], p3 = pos[2][y], dif = 2;
							else p2 = pos[2][y+1], p3 = pos[1][g], dif = 1;
						}
						else if (pre == 1)
						{
							p1 = pos[1][g];

							if (at == 0) p2 = pos[0][r+1], p3 = pos[2][y], dif = 2;
							else p2 = pos[2][y+1], p3 = pos[0][r], dif = 0;
						}
						else
						{
							p1 = pos[2][y];

							if (at == 0) p2 = pos[0][r+1], p3 = pos[1][g], dif = 1;
							else p2 = pos[1][g+1], p3 = pos[0][r], dif = 0;
						}

						ans += max(0, pref[pre][p2]-pref[pre][p1]);
						ans += max(0, pref[dif][p2]-pref[dif][p3]);

						ans += dp[pre][r][g][y];

						if (at == 0)
							dp[at][r+1][g][y] = min(dp[at][r+1][g][y], ans);
						else if (at == 1)
							dp[at][r][g+1][y] = min(dp[at][r][g+1][y], ans);
						else
							dp[at][r][g][y+1] = min(dp[at][r][g][y+1], ans);
					}
				}
			}
		}
	}

	int ans = inf;
	for (int i = 0; i < 3; i++)
		ans = min(ans, dp[i][qtd[0]][qtd[1]][qtd[2]]);

	if (ans == inf)
		printf("-1\n");
	else
		printf("%d\n", ans);
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
joi2019_ho_t3.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25