Submission #235527

#	Time	Username	Problem	Language	Result	Execution time	Memory
235527		davitmarg	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	583 ms	776184 KiB

joi2019_ho_t3

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = 410;

int pr[3][N], n, dp[N][N][N][3], sz[3];
vector<int> pos[3];
string s;

int ind(char x)
{
	if (x == 'R')
		return 0;
	if (x == 'G')
		return 1;
	return 2;
}

int get(int i, int l, int r)
{
	return max(0, pr[i][r] - pr[i][l - 1]);
}


int calc(int x, int a, int b, int c)
{
	a++;
	b++;
	c++;

	int p;
	if (x == 0)
		p = a;
	else if (x == 1)
		p = b;
	else
		p = c;

	int res = 0;
	if (p > pos[x].size())
		return mod;

	if (x != 0 && a <= sz[0])
		res += get(0, pos[0][a - 1], pos[x][p - 1]);
	if (x != 1 && b <= sz[1])
		res += get(1, pos[1][b - 1], pos[x][p - 1]);
	if (x != 2 && c <= sz[2])
		res += get(2, pos[2][c - 1], pos[x][p - 1]);
	return res;
}


void optm()
{
	unordered_map<char, int> c;
	for (int i = 1; i <= n; i++)
		c[s[i]]++;
	vector<pair<int, char>> v;
	v.push_back(MP(c['R'], 'R'));
	v.push_back(MP(c['G'], 'G'));
	v.push_back(MP(c['Y'], 'Y'));
	sort(all(v));
	for (int i = 1; i <= n; i++)
		if (s[i] == 'G')
			s[i] = v[0].second;
		else if (s[i] == 'R')
			s[i] = v[1].second;
		else
			s[i] = v[2].second;
}

int main()
{
	fastIO;
	cin >> n;
	cin >> s;
	s = "#" + s;
	optm();
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
			pr[j][i] = pr[j][i - 1];
		pr[ind(s[i])][i]++;
		pos[ind(s[i])].push_back(i);
	}

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= n; k++)
				dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = mod;


	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	sz[0] = pos[0].size();
	sz[1] = pos[1].size();
	sz[2] = pos[2].size();

	int a, b, k, c, i, j;
	for (k = 0; k < n; k++)
		for (a = 0; a <= k && a <= sz[0]; a++)
			for (b = 0; a + b <= k && b <= sz[1]; b++)
			{
				c = k - a - b;
				if (c > sz[2])
					continue;
				for (j = 0; j < 3; j++)
				{
					int val = calc(j, a, b, c);
					for (i = 0; i < 3; i++)
					{
						if (i == j)
							continue;
						dp[a + (j == 0)][b + (j == 1)][c + (j == 2)][j] = min(dp[a][b][c][i] + val, dp[a + (j == 0)][b + (j == 1)][c + (j == 2)][j]);
					}
				}
			}


	int ans = min(dp[pr[0][n]][pr[1][n]][pr[2][n]][0], min(dp[pr[0][n]][pr[1][n]][pr[2][n]][1], dp[pr[0][n]][pr[1][n]][pr[2][n]][2]));
	if (ans == mod)
		ans = -1;
	cout << ans << endl;

	return 0;
}

/*


*/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int calc(int, int, int, int)':
joi2019_ho_t3.cpp:63:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (p > pos[x].size())
      ~~^~~~~~~~~~~~~~~

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