Submission #245880

#	Time	Username	Problem	Language	Result	Execution time	Memory
245880		pit4h	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	66 ms	4352 KiB

joi2019_ho_t3

#include<bits/stdc++.h>

using namespace std;

const int N = 402, INF = 1e9;
int n, a[N], dp[2][3][N][N], pref[3][N][N];
vector<int> kth_char[3];
string s;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin>>n>>s;

	for(int i=0; i<n; ++i) {
		if(s[i] == 'R') a[i] = 0;
		else if(s[i] == 'G') a[i] = 1;
		else a[i] = 2;
	}
	
	for(int c=0; c<3; ++c) {
		kth_char[c].push_back(-1);
		
	}
	for(int i=0; i<n; ++i) {
		kth_char[a[i]].push_back(i);
	}
	
	for(int c=0; c<3; ++c) {
		for(int i=0; i<(int)kth_char[c].size(); ++i) {
			int cnt = i;
			for(int j=0; j<n; ++j) {
				if(j!=0) pref[c][i][j] = pref[c][i][j-1];
				if(cnt>0 && a[j]==c) {
					pref[c][i][j] ++;
					cnt --;
				}
			}
		}
	}

	for(int c=0; c<3; ++c) {
		for(int i=0; i<=n; ++i) {
			for(int j=0; j<=n; ++j) {
				dp[1][c][i][j] = INF;
			}
		}
		dp[1][c][0][0] = 0;
	}

	
	for(int it=0; it<n; ++it) {

		for(int c=0; c<3; ++c) {
			for(int i=0; i<(int)kth_char[0].size(); ++i) {
				for(int j=0; j<(int)kth_char[1].size(); ++j) {
					int k = it+1 - i - j;
					dp[it%2][c][i][j] = INF;
					if(k < 0 || k >= (int)kth_char[2].size()) continue;
					
					if(c==0 && i>0) {
						int pos = kth_char[c][i];
						dp[it%2][c][i][j] = min(dp[(it+1)%2][1][i-1][j], dp[(it+1)%2][2][i-1][j]) + pos + 1 - (pref[0][i][pos] + pref[1][j][pos] + pref[2][k][pos]) ;
					}
					if(c==1 && j>0) {
						int pos = kth_char[c][j];
						dp[it%2][c][i][j] = min(dp[(it+1)%2][0][i][j-1], dp[(it+1)%2][2][i][j-1]) + pos + 1 - (pref[0][i][pos] + pref[1][j][pos] + pref[2][k][pos]) ;
					}
					if(c==2 && k>0) {
						int pos = kth_char[c][k];
						dp[it%2][c][i][j] = min(dp[(it+1)%2][0][i][j], dp[(it+1)%2][1][i][j]) + pos + 1 - (pref[0][i][pos] + pref[1][j][pos] + pref[2][k][pos]) ;
					}
				}
			}
		}

	}

	int ans = INF;
	for(int c=0; c<3; ++c) {
		ans = min(ans, dp[(n-1)%2][c][kth_char[0].size()-1][kth_char[1].size()-1]);
	}

	if(ans < INF) cout<<ans;
	else cout<<-1;
}

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