Submission #116795

#	Time	Username	Problem	Language	Result	Execution time	Memory
116795		ZwariowanyMarcin	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	5 / 100	118 ms	163072 KiB

joi2019_ho_t3

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


#define pb push_back
#define ld long double
#define fi first
#define se second
#define ll long long
#define ss(x) (int) x.size()
#define mp make_pair
#define FOR(i, n) for(int i = 1; n >= i; ++i)

using namespace std;
using namespace __gnu_pbds;

const int inf = 1e9 + 1;

int dp[405][405][405][3];
int n;
string s;
int cnt[405][3];
int t[405];
vector <int> v[3];
int ile[3];
		

int main() {
	
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin >> n >> s;
	for(int i = 0; i < n; ++i) {
		if(s[i] == 'R')
			t[i + 1] = 0;
		if(s[i] == 'G')
			t[i + 1] = 1;
		if(s[i] == 'Y')
			t[i + 1] = 2;
	}
	for(int i = 0; i < 3; ++i) {
		v[i].pb(0);
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j < 3; ++j) 
			cnt[i][j] = cnt[i - 1][j];
		cnt[i][t[i]]++;
		v[t[i]].pb(i);
	}
	int R = cnt[n][0];
	int G = cnt[n][1];
	int Y = cnt[n][2];
	for(int r = 0; r <= R; ++r) 
		for(int g = 0; g <= G; ++g)
			for(int y = 0; y <= Y; ++y)
				for(int z = 0; z < 3; ++z)
					dp[r][g][y][z] = inf;
	
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	
	int maxi = max({R, G, Y});
	if(maxi > n / 2 + 1) {
		cout << -1;
		return 0;
	}
	
	for(int r = 0; r <= R; ++r)
		for(int g = 0; g <= G; ++g)
			for(int y = 0; y <= Y; ++y) {
				for(int last = 0; last < 3; ++last) {
					
					int ans = dp[r][g][y][last];
					
					ile[0] = r;
					ile[1] = g;
					ile[2] = y;
					
					for(int i = 0; i < 3; ++i) {
						if(i == last || ile[i] + 1 == ss(v[i])) 
							continue;
						
						int pos = v[i][ile[i] + 1];
						int add = -1 + pos - r - g - y;
						
						for(int j = 0; j < 3; ++j) {
							int ost = v[j][ile[j]];
							add += max(0, cnt[ost][j] - cnt[pos][j]);
						}
						//cout << r << " " << g << " " << y << " " << " " << i << " " << ans << endl;
						ile[i]++;
						dp[ile[0]][ile[1]][ile[2]][i] = min(dp[ile[0]][ile[1]][ile[2]][i], add + ans);
						ile[i]--;
					}
				}
			}
	int best = inf;
	for(int i = 0; i < 3; ++i) 
		best = min(best, dp[R][G][Y][i]);
	cout << best;
		
	
						
	
	
	
	
	
	
	
    return 0;
}

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