Submission #459554

#	Time	Username	Problem	Language	Result	Execution time	Memory
459554		TeaTime	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	485 ms	809704 KiB

joi2019_ho_t3

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef int ll;
typedef long double ld;

const ll K = 410, INF = 1e9;

ll n;
ll dp[K][K][K][3];
ll cnt[3];
ll pos[3][K];
tuple<ll, ll, ll> prefCnt[K];

int main() {
	fastInp;

	cin >> n;
	string s;
	cin >> s;
	
	int i = 1;
	for (auto &c : s) {
		if (c == 'R') c = 0;
		if (c == 'G') c = 1;
		if (c == 'Y') c = 2;
		cnt[c]++;
		pos[c][cnt[c]] = i;
		prefCnt[i] = { cnt[0], cnt[1], cnt[2] };
		i++;
	}

	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K; j++) {
			for (int k = 0; k < K; k++) {
				for (int t = 0; t < 3; t++) dp[i][j][k][t] = INF;
			}
		}
	}

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

	for (int i = 0; i <= cnt[0]; i++) {
		for (int j = 0; j <= cnt[1]; j++) {
			for (int k = 0; k <= cnt[2]; k++) {
				for (int add = 0; add < 3; add++) {
					ll pn = 0;
					ll ind;

					if (add == 0) {
						ind = pos[add][i + 1];
						pn = max(0, get<1>(prefCnt[ind]) - j) + max(0, get<2>(prefCnt[ind]) - k);
					} else if (add == 1) {
						ind = pos[add][j + 1];
						pn = max(0, get<0>(prefCnt[ind]) - i) + max(0, get<2>(prefCnt[ind]) - k);
					} else {
						ind = pos[add][k + 1];
						pn = max(0, get<0>(prefCnt[ind]) - i) + max(0, get<1>(prefCnt[ind]) - j);
					}

					for (int t = 0; t < 3; t++) {
						if (add == t) continue;

						ll cnt = dp[i][j][k][t] + pn;
						if (add == 0) {
							dp[i + 1][j][k][add] = min(dp[i + 1][j][k][add], cnt);
						} else if (add == 1) {
							dp[i][j + 1][k][add] = min(dp[i][j + 1][k][add], cnt);
						} else {
							dp[i][j][k + 1][add] = min(dp[i][j][k + 1][add], cnt);
						}
					}
				}
			}
		}
	}
	ll a = INF;
	for (int i = 0; i < 3; i++) a = min(a, dp[cnt[0]][cnt[1]][cnt[2]][i]);
	
	if (a >= INF) {
		cout << "-1\n";
	} else {
		cout << a;
	}

	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:39:7: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |   cnt[c]++;
      |       ^
joi2019_ho_t3.cpp:40:7: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |   pos[c][cnt[c]] = i;
      |       ^
joi2019_ho_t3.cpp:40:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |   pos[c][cnt[c]] = i;
      |              ^

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