Submission #287786

#	Time	Username	Problem	Language	Result	Execution time	Memory
287786		reymontada61	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	631 ms	1040344 KiB

joi2019_ho_t3

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

int n;
string s;
int r, g, b;
const int MXN = 405;
int dp[MXN][MXN][MXN][4];

vector<int> rs, gs, bs;

int best(int ind, int r, int g, int b, int whi) {
	if (ind == -1) return 0;
	if (dp[ind][r][g][whi] != -1) return dp[ind][r][g][whi];
	int bt = INT_MAX / 2;
	if (r > 0 && whi != 1) {
		bt = min(bt, best(ind-1, r-1, g, b, 1) + abs(rs[r-1] - ind));
	}
	if (g > 0 && whi != 2) {
		bt = min(bt, best(ind-1, r, g-1, b, 2) + abs(gs[g-1] - ind));
	}
	if (b > 0 && whi != 3) {
		bt = min(bt, best(ind-1, r, g, b-1, 3) + abs(bs[b-1] - ind));
	}
	return dp[ind][r][g][whi] = bt;
}

signed main() {

	for (int i=0; i<MXN; i++) {
		for (int j=0; j<MXN; j++) {
			for (int l=0; l<MXN; l++) {
				for (int k=0; k<4; k++) {
					dp[i][j][l][k] = -1;
				}
			}
		}
	}

	cin >> n >> s;
	
	for (int i=0; i<n; i++) {
		if (s[i] == 'R') {
			rs.push_back(i);
			r++;
		}
		if (s[i] == 'G') {
			gs.push_back(i);
			g++;
		}
		if (s[i] == 'Y') {
			bs.push_back(i);
			b++;
		}
	}
	
	int re = best(n-1, r, g, b, 0);
	
	if (re > n * n) {
		cout << -1 << endl;
	}
	else {
		cout << re / 2 << endl;
	}

}

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