Submission #1145841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145841		nuutsnoynton	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	351 ms	761040 KiB

joi2019_ho_t3

#include<bits/stdc++.h>

using namespace std;
using ll = int;
const ll N = 402;
ll rg[N], ry[N], gr[N], gy[N], yr[N], yg[N];
ll dp[N][N][N][3];
vector < ll > red, green, yellow;
int main() {
	ll n, m, r, x, y, i, j, cnt, s, R, G, Y, ans, t, g_cnt, y_cnt, r_cnt;
	string str;
	
	cin >> n >> str;
	
	str = "." + str;
	for ( R = 0; R <= n; R ++) for ( G = 0; G <= n; G ++) for ( Y = 0; Y <= n; Y ++ ) for ( r = 0; r <= 2; r ++) dp[R][G][Y][r] = 1e9;
	
	for (i = 1; i <= n; i++) {
		if ( str[i] == 'R') red.push_back(i);
		if ( str[i] == 'G') green.push_back(i);
		if ( str[i] == 'Y') yellow.push_back(i);
	}
	r_cnt = y_cnt = g_cnt = 0;
	for (i = 0; i < red.size(); i ++) {
		rg[i + 1] = lower_bound(green.begin(), green.end(), red[i]) - green.begin();
		ry[i + 1] = lower_bound(yellow.begin(), yellow.end(), red[i]) - yellow.begin();
	}
	for (i = 0; i < green.size(); i ++) {
		gr[i + 1] = lower_bound(red.begin(), red.end(), green[i]) - red.begin();
		gy[i + 1] = lower_bound(yellow.begin(), yellow.end(), green[i]) - yellow.begin();
	}
	for (i = 0; i < yellow.size(); i ++) {
		yg[i + 1] = lower_bound(green.begin(), green.end(), yellow[i]) - green.begin();
		yr[i + 1] = lower_bound(red.begin(), red.end(), yellow[i]) - red.begin();
	}
	
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	for ( R = 0; R <= red.size(); R ++) {
		for (G = 0; G <= green.size(); G ++) {
			for ( Y = 0; Y <= yellow.size(); Y ++) {
			// r = 0
		//	cout << R << " " << G << " " << Y << endl;
				if ( R > 0 ) {
					cnt = red[R - 1] - (R - 1);
					cnt -= min(G, rg[R]);
					cnt -= min(Y, ry[R]);
					dp[R][G][Y][0] = min(dp[R][G][Y][0], dp[R - 1][G][Y][1] + cnt - 1);
					dp[R][G][Y][0] = min(dp[R][G][Y][0], dp[R - 1][G][Y][2] + cnt - 1);
				}
			// r = 1
				if ( G > 0 ) {
					cnt = green[G - 1] - (G - 1);
					cnt -= min(R, gr[G]);
					cnt -= min(Y, gy[G]);
					dp[R][G][Y][1] = min(dp[R][G][Y][1], dp[R][G - 1][Y][0] + cnt - 1);
					dp[R][G][Y][1] = min(dp[R][G][Y][1], dp[R][G - 1][Y][2] + cnt - 1);
				}
			// r = 2;
				if ( Y > 0) {
					cnt = yellow[Y - 1] - (Y - 1); 
					cnt -= min(R, yr[Y]);
					cnt -= min(G, yg[Y]);
					
					dp[R][G][Y][2] = min(dp[R][G][Y][2], dp[R][G][Y - 1][0] + cnt - 1);
					dp[R][G][Y][2] = min(dp[R][G][Y][2], dp[R][G][Y - 1][1] + cnt - 1);
				}
			}
		}
	}
//	cout << "HI" << "\n"<< endl;
	s = 1e9;
	s = min(s,  dp[red.size()][green.size()][yellow.size()][0]);
	s = min(s,  dp[red.size()][green.size()][yellow.size()][1]);
	s = min(s,  dp[red.size()][green.size()][yellow.size()][2]);
	if ( s == 1e9) cout << -1 << endl;
	else cout << s << endl;
}

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