Submission #532862

#	Time	Username	Problem	Language	Result	Execution time	Memory
532862		amunduzbaev	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	519 ms	1048580 KiB

joi2019_ho_t3

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 405;
int dp[N][N][N][3];
vector<int> in[3];
int pos[3][N][3];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	string s; cin>>s;
	ar<int, 3> sz {};
	for(int i=0;i<n;i++){
		if(s[i] == 'R') in[0].push_back(i), sz[0]++;
		if(s[i] == 'G') in[1].push_back(i), sz[1]++;
		if(s[i] == 'Y') in[2].push_back(i), sz[2]++;
	}
	
	for(int t=0;t<3;t++){
		for(int i=0;i<sz[t];i++){
			for(int k=0;k<3;k++){
				for(int j=0;j<sz[k];j++){
					if(in[k][j] > in[t][i]) break;
					pos[t][i][k]++;
				}
			}
		}
	}
	
	memset(dp, 127, sizeof dp);
	dp[0][0][0][0] = 
	dp[0][0][0][1] = 
	dp[0][0][0][2] = 0;
	
	for(int i=0;i<=sz[0];i++){
		for(int j=0;j<=sz[1];j++){
			for(int l=0;l<=sz[2];l++){
				if(i < sz[0]){
					int cc = max(0ll, pos[0][i][1] - j) + max(0ll, pos[0][i][2] - l);
					dp[i+1][j][l][0] = min(dp[i+1][j][l][0], dp[i][j][l][1] + cc);
					dp[i+1][j][l][0] = min(dp[i+1][j][l][0], dp[i][j][l][2] + cc);
				} if(j < sz[1]){
					int cc = max(0ll, pos[1][j][0] - i) + max(0ll, pos[1][j][2] - l);
					dp[i][j+1][l][1] = min(dp[i][j+1][l][1], dp[i][j][l][0] + cc);
					dp[i][j+1][l][1] = min(dp[i][j+1][l][1], dp[i][j][l][2] + cc);
				} if(l < sz[2]){
					int cc = max(0ll, pos[2][l][0] - i) + max(0ll, pos[2][l][1] - j);
					dp[i][j][l+1][2] = min(dp[i][j][l+1][2], dp[i][j][l][0] + cc);
					dp[i][j][l+1][2] = min(dp[i][j][l+1][2], dp[i][j][l][1] + cc);
				}
			}
		}
	}
	
	int res = 1e9;
	for(int i=0;i<3;i++) res = min(res, dp[sz[0]][sz[1]][sz[2]][i]);
	if(res < 1e9) cout<<res<<"\n";
	else cout<<-1<<"\n";
}

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