Submission #163524

#TimeUsernameProblemLanguageResultExecution timeMemory
163524nvmdavaGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
100 / 100
469 ms163092 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 405
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
 
char c;
int dp[N][N][N][3];
int a[N];
vector<int> app[3];
 
int i[3];

int cost(int k){
	i[k]--;
	int res = INF;
	for(int r = 0; r < 3; ++r)
		if(r != k)
			res = min(res, dp[i[0]][i[1]][i[2]][r]);
	
	int v = app[k][i[k]];
	i[k]++;
	int w = v;
	for(int j = 0; j < 3; j++){
		int a = upper_bound(app[j].begin(), app[j].begin() + i[j], v) - app[j].begin();
		w += max(0, i[j] - a);
	}
 
	return res + abs(i[0] + i[1] + i[2] - w);
}

int s[3];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin>>n;
 
    for(int i = 1; i <= n; i++){
    	cin>>c;
    	if(c == 'R')
    		app[0].push_back(i);
    	else if(c == 'G')
    		app[1].push_back(i);
    	else
    		app[2].push_back(i);
    }

    for(int i = 0; i < 3; ++i)
    	s[i] = app[i].size();

    for(i[0] = 0; i[0] <= s[0]; ++i[0]){
    	for(i[1] = 0; i[1] <= s[1]; ++i[1]){
    		for(i[2] = 0; i[2] <= s[2]; ++i[2]){
    			for(int k = 0; k < 3; ++k){

    				if(i[0] + i[1] + i[2] == 0)
    					dp[i[0]][i[1]][i[2]][k] = 0;
    				else if(i[k] == 0)
	    				dp[i[0]][i[1]][i[2]][k] = INF;
	    			else
 		   				dp[i[0]][i[1]][i[2]][k] = cost(k);
    			}
    		}
    	}
    }
    int res = min(dp[s[0]][s[1]][s[2]][0], min(dp[s[0]][s[1]][s[2]][1], dp[s[0]][s[1]][s[2]][2]));
    if(res == 0x3f3f3f3f)
    	cout<<-1;
    else
    	cout<<res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...