Submission #429121

#	Time	Username	Problem	Language	Result	Execution time	Memory
429121		Berted	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	236 ms	7876 KiB

joi2019_ho_t3

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const ll INF = 1e18;

int N, cnt[3][3][401]; string S;

vector<int> A[3];
ll DP[2][3][401][401];

int main()
{
	cin >> N >> S;
	for (int i = 1; i <= N; i++)
	{
		if (S[i - 1] == 'R') 
		{
			A[0].push_back(i);
			for (int j = 0; j < 3; j++) cnt[0][j][A[0].size() - 1] = A[j].size();
		}
		else if (S[i - 1] == 'G') 
		{
			A[1].push_back(i);
			for (int j = 0; j < 3; j++) cnt[1][j][A[1].size() - 1] = A[j].size();
		}
		else 
		{
			A[2].push_back(i);
			for (int j = 0; j < 3; j++) cnt[2][j][A[2].size() - 1] = A[j].size();
		}
	}

	for (int s = 0; s < 3; s++)
		for (int i = 0; i <= N; i++)
			for (int j = 0; j <= N; j++) DP[0][s][i][j] = INF;

	for (int s = 0; s < 3; s++) DP[0][s][0][0] = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int s = 0; s < 3; s++)
			for (int j = 0; j <= N; j++)
				for (int k = 0; k <= N; k++) DP[i & 1][s][j][k] = INF;

		for (int s = 0; s < 3; s++)
		{
			for (int j = 0; j <= i && j <= A[0].size(); j++)
			{
				for (int k = 0; k + j <= i && k <= A[1].size(); k++)
				{
					int l = i - j - k;
					if (l > A[2].size()) continue;

					if (s == 0 && j) 
					{
						for (int t = 0; t < 3; t++)
						{
							if (s == t) continue;
							DP[i & 1][s][j][k] = min(DP[i & 1][s][j][k], DP[~i & 1][t][j - 1][k] + max(0, cnt[s][1][j - 1] - k) + max(0, cnt[s][2][j - 1] - l));
						}
					}

					if (s == 1 && k)
					{
						for (int t = 0; t < 3; t++)
						{
							if (s == t) continue;
							DP[i & 1][s][j][k] = min(DP[i & 1][s][j][k], DP[~i & 1][t][j][k - 1] + max(0, cnt[s][0][k - 1] - j) + max(0, cnt[s][2][k - 1] - l));
						}
					}

					if (s == 2 && l)
					{
						for (int t = 0; t < 3; t++)
						{
							if (s == t) continue;
							DP[i & 1][s][j][k] = min(DP[i & 1][s][j][k], DP[~i & 1][t][j][k] + max(0, cnt[s][0][l - 1] - j) + max(0, cnt[s][1][l - 1] - k));
						}
					}

					//if (DP[i & 1][s][j][k] < INF) cout << i << " " << s << " " << j << " " << k << " " << l << " " << DP[i & 1][s][j][k] << "\n";
				}
			}
		}
	}

	ll res = INF;
	for (int s = 0; s < 3; s++) {res = min(res, DP[N & 1][s][A[0].size()][A[1].size()]);}

	if (res == INF) cout << "-1\n";
	else 
	{
		cout << res << "\n";
	}
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:49:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    for (int j = 0; j <= i && j <= A[0].size(); j++)
      |                              ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:51:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int k = 0; k + j <= i && k <= A[1].size(); k++)
      |                                   ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:54:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |      if (l > A[2].size()) continue;
      |          ~~^~~~~~~~~~~~~

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