Submission #235519

#	Time	Username	Problem	Language	Result	Execution time	Memory
235519		davitmarg	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	712 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];
vector<int> pos[3];
string s;

inline 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]);
}

inline 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 <= pos[0].size())
		res += get(0, pos[0][a - 1], pos[x][p - 1]);
	if (x != 1 && b <= pos[1].size())
		res += get(1, pos[1][b - 1], pos[x][p - 1]);
	if (x != 2 && c <= pos[2].size())
		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;
	for (int k = 0; k < n; k++)
		for (int a = 0; a <= k && a <= pos[0].size(); a++)
			for (int b = 0; a + b <= k && b <= pos[1].size(); b++)
			{
				int c = k - a - b;

				for (int j = 0; j < 3; j++)
				{
					int val = calc(j, a, b, c);
					for (int 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;
}

/*


RG



*/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int calc(int, int, int, int)':
joi2019_ho_t3.cpp:62:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (p > pos[x].size())
      ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (x != 0 && a <= pos[0].size())
                ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (x != 1 && b <= pos[1].size())
                ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (x != 2 && c <= pos[2].size())
                ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:117:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int a = 0; a <= k && a <= pos[0].size(); a++)
                             ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:118:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int b = 0; a + b <= k && b <= pos[1].size(); b++)
                                  ~~^~~~~~~~~~~~~~~~

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