Submission #542464

#	Time	Username	Problem	Language	Result	Execution time	Memory
542464		pooyashams	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	38 ms	2004 KiB

joi2019_ho_t3

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 410;
const int inf = 1e8;

int dp[2][maxn][maxn][3];
int idxs[3][maxn];
int ps[maxn][3];
int cnt[3];

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	string _s; cin >> _s;
	vector<int> s;
	for(int i = 0; i < n; i++)
	{
		char ch = _s[i];
		if(ch == 'R')
			s.push_back(0);
		else if(ch == 'G')
			s.push_back(1);
		else
			s.push_back(2);
		idxs[s.back()][cnt[s.back()]++] = i;
		for(int j = 0; j < 3; j++)
			ps[i+1][j] = ps[i][j];
		ps[i+1][s.back()]++;
	}
	if(2*max(cnt[0], max(cnt[1], cnt[2])) > n+1)
	{
		cout << -1 << endl;
		return 0;
	}
	//for(int i = 0; i <= n; i++)
	//	//cerr << ps[i][0] << " " << ps[i][1] << " " << ps[i][2] << endl;
	for(int x = 0; x < 2; x++)
		for(int y = 0; y <= cnt[1]; y++)
			for(int z = 0; z <= cnt[2]; z++)
				for(int c = 0; c < 3; c++)
					dp[x][y][z][c] = inf;
	for(int x = 0; x <= cnt[0]; x++)
	{
		for(int y = 0; y <= cnt[1]; y++)
			for(int z = 0; z <= cnt[2]; z++)
				for(int c = 0; c < 3; c++)
					dp[x&1][y][z][c] = inf;
		for(int y = 0; y <= cnt[1]; y++)
		{
			for(int z = 0; z <= cnt[2]; z++)
			{
				if(x == 0 and y == 0 and z == 0)
				{
					dp[x&1][y][z][0] = 0;
					dp[x&1][y][z][1] = 0;
					dp[x&1][y][z][2] = 0;
					continue;
				}
				if(x > 0)
				{
					int i = idxs[0][x-1];
					int a = i - min(ps[i][0],x) - min(ps[i][1],y) - min(ps[i][2],z);
					dp[x&1][y][z][0] = min(dp[!(x&1)][y][z][1], dp[!(x&1)][y][z][2]) + a;
					////cerr << a << " ";
				}
				if(y > 0)
				{
					int i = idxs[1][y-1];
					int a = i - min(ps[i][0],x) - min(ps[i][1],y) - min(ps[i][2],z);
					dp[x&1][y][z][1] = min(dp[x&1][y-1][z][0], dp[x&1][y-1][z][2]) + a;
					//cerr << a << " ";
				}
				if(z > 0)
				{
					int i = idxs[2][z-1];
					int a = i - min(ps[i][0],x) - min(ps[i][1],y) - min(ps[i][2],z);
					dp[x&1][y][z][2] = min(dp[x&1][y][z-1][0], dp[x&1][y][z-1][1]) + a;
					//cerr << a << " ";
				}
				//cerr << endl;
				//cerr << x << "," << y << "," << z << ": " << dp[x&1][y][z][0] << " " << dp[x&1][y][z][1] << " " << dp[x&1][y][z][2] << endl;
			}
		}
	}
	int ans = min(dp[cnt[0]&1][cnt[1]][cnt[2]][0], min(dp[cnt[0]&1][cnt[1]][cnt[2]][1], dp[cnt[0]&1][cnt[1]][cnt[2]][2]));
	if(ans >= inf)
		ans = -1;
	cout << ans << endl;
	return 0;
}

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