Submission #586380

#	Time	Username	Problem	Language	Result	Execution time	Memory
586380		blue	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	74 ms	28764 KiB

joi2019_ho_t3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

const int INF = 1'000'000;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	string s;
	cin >> s;
	s = " " + s;

	vi lst[3];

	vvi ct(1+N, vi(3, 0));

	for(int u = 0; u <= 2; u++)
		lst[u].push_back(0);

	vi S(1+N);
	for(int i = 1; i <= N; i++)
	{
		if(s[i] == 'R')
			S[i] = 0;
		else if(s[i] == 'G')
			S[i] = 1;
		else
			S[i] = 2;

		ct[i] = ct[i-1];
		ct[i][S[i]]++;

		lst[S[i]].push_back(i);
	}

	int DP[1 + ct[N][0]][1 + ct[N][1]][1 + ct[N][2]][3];
	for(int a = 0; a <= ct[N][0]; a++)
		for(int b = 0; b <= ct[N][1]; b++)
			for(int c = 0; c <= ct[N][2]; c++)
				for(int x = 0; x <= 2; x++)
					DP[a][b][c][x] = INF;

	for(int x = 0; x <= 2; x++)
		DP[0][0][0][x] = 0;

	for(int a = 0; a <= ct[N][0]; a++)
	{
		for(int b = 0; b <= ct[N][1]; b++)
		{
			for(int c = 0; c <= ct[N][2]; c++)
			{
				for(int x = 0; x <= 2; x++)
				{
					int na = a, nb = b, nc = c;

					if(x == 0 && a == 0)
						continue;

					if(x == 1 && b == 0)
						continue;

					if(x == 2 && c == 0)
						continue;

					int pos;
					if(x == 0)
						pos = lst[0][a];
					else if(x == 1)
						pos = lst[1][b];
					else
						pos = lst[2][c];

					int delta = abs(ct[pos][0] - a) + abs(ct[pos][1] - b) + abs(ct[pos][2] - c);

					if(x == 0)
						na--;
					else if(x == 1)
						nb--;
					else
						nc--;

					for(int y = 0; y <= 2; y++)
					{
						if(y == x) continue;

						DP[a][b][c][x] = min(DP[a][b][c][x], DP[na][nb][nc][y] + delta);
					}
				}
			}
		}
	}

	int res = INF;
	for(int x = 0; x <= 2; x++)
		res = min(res, DP[ct[N][0]][ct[N][1]][ct[N][2]][x]);

	if(res >= N*N)
		res = -1;
	else
		res /= 2;

	cout << res << '\n';
}

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