Submission #886331

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

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 407;
constexpr int oo = 1e9;
int sumpref[MAXN][3];
int POS[MAXN][MAXN][MAXN][3];
int dp[MAXN][MAXN][MAXN][3];
vector<int> idx[3];
int R,G,Y;
int n;

int check(int i, int j, int k, int v){
	int ith, sum = 0;
	if(v == 0)
		ith = idx[v][i-1];
	if(v == 1)
		ith = idx[v][j-1];
	if(v == 2)
		ith = idx[v][k-1];
	
	sum += max(sumpref[ith][0], i);
	sum += max(sumpref[ith][1], j);
	sum += max(sumpref[ith][2], k);
	
	return sum;
}

void computePos(){
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 1; k <= n; k++){
				if(k <= R && i <= G && j <= Y)
					POS[k][i][j][0] = check(k, i, j, 0);
				if(i <= R && k <= G && j <= Y)
					POS[i][k][j][1] = check(i, k, j, 1);
				if(i <= R && j <= G && k <= Y)
					POS[i][j][k][2] = check(i, j, k, 2);
			}
		}
	}
}

void solve(){
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k <= n; k++)
				dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = oo;
				
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	
	
	//dp[i][j][k][v]
	// i -> pozycja
	// j -> ile R
	// k -> ile G
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= min(R, i); j++){
			for(int k = 0; k <= min(G, i); k++){
				//dla 0 -> {1, 2}
				//dla 1 -> {0, 2}
				//dla 2 -> {1, 2}
				
				//na pozycji itej stawiamy R
				if(j && j+k <= i)
					dp[i][j][k][0] = min(dp[i-1][j-1][k][1], dp[i-1][j-1][k][2]) + abs(i - POS[j][k][i - (j+k)][0]);
				
				//na pozycji itej stawiamy G
				if(k && j+k <= i)
					dp[i][j][k][1] = min(dp[i-1][j][k-1][0], dp[i-1][j][k-1][2]) + abs(i - POS[j][k][i - (j+k)][1]);
				
				//na pozycji itej stawiamy Y
				if(i >= j+k && (i - (j+k) <= Y))
					dp[i][j][k][2] = min(dp[i-1][j][k][0], dp[i-1][j][k][1]) + abs(i - POS[j][k][i - (j+k)][2]);
			
			}
		}
	}

}

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

	computePos();
	solve();
	
	int res = min({dp[n][R][G][0], dp[n][R][G][1], dp[n][R][G][2]});
	if(res == oo) cout << "-1 \n";
	else cout << res << "\n";
	
}

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