Submission #542319

#	Time	Username	Problem	Language	Result	Execution time	Memory
542319		Arnch	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	137 ms	163008 KiB

joi2019_ho_t3

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x

constexpr int N = 410, inf = 510510;

int dp[N][N][N][3], ind[3][N], tim[3], pr[N][3];

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n; cin >>n;
	string s; cin >>s;

	s = '#' + s;

	for(int i = 1; i <= n; i++) {
		if(s[i] == 'R') s[i] = 'a';
		else if(s[i] == 'G') s[i] = 'b';
		else s[i] = 'c';
	}

	for(int i = 1; i <= n; i++) {
		ind[s[i] - 'a'][++tim[s[i] - 'a']] = i;
	}
	
	int cnt0 = 0, cnt1 = 0, cnt2 = 0;
	for(int i = 1; i <= n; i++) {
		if(s[i] - 'a' == 0) cnt0++;
		else if(s[i] - 'a' == 1) cnt1++;
		else cnt2++;
	}
	
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= 2; j++) pr[i][j] = pr[i - 1][j];
		pr[i][s[i] - 'a']++;
	}

    for(int i = 0; i <= cnt0; i++) {
        for(int j = 0; j <= cnt1; j++) {
            for(int k = 0; k <= cnt2; k++) {
                for(int f = 0; f <= 2; f++) {
                    dp[i][j][k][f] = inf;
                }
            }
        }
    }

	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	int ans;

	for(int i = 0; i <= cnt0; i++)
		for(int j = 0; j <= cnt1; j++) 
			for(int k = 0; k <= cnt2; k++) 
				for(int l = 0; l <= 2; l++) 
					for(int cur = 0; cur <= 2; cur++) {
						if(cur == l) continue;
						if(cur == 0 && cnt0 == i) continue;
						if(cur == 1 && cnt1 == j) continue;
						if(cur == 2 && cnt2 == k) continue;
					
						int pos1 = 0, pos2 = 0, pos3 = 0;
						int res = 3 - l - cur;
						if(l == 0) {
							pos1 = ind[0][i];
							if(cur == 1) pos2 = ind[1][j + 1], pos3 = ind[2][k];
							else pos2 = ind[2][k + 1], pos3 = ind[1][j];
						}
						else if(l == 1) {
							pos1 = ind[1][j];
							if(cur == 0) pos2 = ind[0][i + 1], pos3 = ind[2][k];
							else pos2 = ind[2][k + 1], pos3 = ind[0][i];
						}
						else if(l == 2) {
							pos1 = ind[2][k];
							if(cur == 0) pos2 = ind[0][i + 1], pos3 = ind[1][j];
							else pos2 = ind[1][j + 1], pos3 = ind[0][i];
						}
						ans = 0;
						ans += max(0, pr[pos2][l] - pr[pos1][l]);
						ans += max(0, pr[pos2][res] - pr[pos3][res]);
						ans += dp[i][j][k][l];

						if(cur == 0) {
							dp[i + 1][j][k][cur] = min(dp[i + 1][j][k][cur], ans);
						}		
						else if(cur == 1) {
							dp[i][j + 1][k][cur] = min(dp[i][j + 1][k][cur], ans);
						}
						else {
							dp[i][j][k + 1][cur] = min(dp[i][j][k + 1][cur], ans);
						}
					}

	ans = inf;
	for(int i = 0; i < 3; i++) ans = min(ans, dp[cnt0][cnt1][cnt2][i]);

	if(ans >= inf) cout<<-1;
	else cout<<ans;

    return 0;
}

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