Submission #1089447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089447		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	244 ms	687696 KiB

joi2019_ho_t3

//don't copy pls)
/*TAAK ZDES NADO RECURSIU PISAT*/

//I'm not in the danger i am the DANGER
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define sigma signed
using namespace std;
using namespace __gnu_pbds;
const int N = 400 + 1;
int mod = 1e9 + 7;
const int INF = 1e18;
int n,p[3][N];
vector <int> g[3];
int cnt1 , cnt2 , cnt3;
string s,t;
vector <string> q;
int dp[N][N][N][3];
void Gold(){
	cin >> n >> s;
	s = '+' + s;
	t.pb('R');
	t.pb('Y');
	t.pb('G');
	for(int i = 1 ; i <= n ; i++){
		if(s[i] == 'R'){
			cnt1++;
		}
		if(s[i] == 'Y'){
			cnt2++;
		}
		if(s[i] == 'G'){
			cnt3++;
		}
		for(int j = 0 ; j < 3 ; j++){
			p[j][i] = p[j][i - 1] + (s[i] == t[j]);
		}
	}
	for(int i = 1 ; i <= n ; i++){
		for(int j = 0 ; j <= cnt1 ; j++){
			for(int k = 0 ; k <= cnt2 ; k++){
				for(int y = 0 ; y < 3 ; y++){
					dp[i][j][k][y] = INF;
				}
			}
		}
	}
	for(int y = 0 ; y < 3 ; y++){
		dp[0][0][0][y] = 0;
	}
	for(int i = 1 ; i <= n ; i++){
		for(int j = 0 ; j < 3 ; j++){
			if(s[i] == t[j]){
				g[j].pb(i);
			}
		}
	}
//	cout << "ok";
	for(int i = 1 ; i <= n ; i++){
		for(int a = 0 ; a <= cnt1 ; a++){
			for(int b = 0 ; b <=cnt2 ; b++){
				if(a+b>i) continue;
				int c = i - (a + b);
				if(c > cnt3) continue;
				if(a){
					int pos = g[0][a - 1];
					int cnt = max(0ll,(b - p[1][pos])) + max((c - p[2][pos]) , 0ll);
					dp[i][a][b][0] = min(dp[i - 1][a - 1][b][1] , dp[i - 1][a - 1][b][2]) + max(0ll , (pos + cnt) - i);
				}
				if(b){
					int pos = g[1][b - 1];
					int cnt = max(a - p[0][pos] , 0ll) + max(c - p[2][pos] , 0ll);
					dp[i][a][b][1] = min(dp[i - 1][a][b - 1][0] , dp[i - 1][a][b - 1][2]) + max(0ll , (pos + cnt) - i);
				}
				if(c){
					int pos = g[2][c - 1];
					int cnt = max(0ll , a - p[0][pos]) + max(0ll , b - p[1][pos]);
					dp[i][a][b][2] = min(dp[i - 1][a][b][0] , dp[i - 1][a][b][1]) + max(0ll , (pos + cnt) - i);
				}
				// cout << i << ' ' << a << ' ' << b << ' ' << c << '\n';
			}
		}
	}
	int ans = INF;
	for(int i = 0 ; i < 3 ; i++){
		ans = min(ans , dp[n][cnt1][cnt2][i]);
	}
	if(ans == INF){
		cout << "-1\n";
		return;
	}
	cout << ans;
	
}
sigma main(){
	//freopen("txt.in","r",stdin);
	//freopen("txt.out","w",stdout);
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
	int TT = 1;
	// cin >> TT;
	for(int i = 1 ; i <= TT ; i++){
		//cout << "Case " << i << ": ";
		Gold();
	}
}

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