Submission #459547

#	Time	Username	Problem	Language	Result	Execution time	Memory
459547		TeaTime	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	5 / 100	512 ms	972148 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], pnlty[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 t = 0; t < 3; t++) {
					ll ind;
					
					if (t == 0) {
						ind = pos[t][i + 1];
						ll a = max(0, get<0>(prefCnt[ind]) - i);
						ll b = max(0, get<1>(prefCnt[ind]) - j);
						ll c = max(0, get<2>(prefCnt[ind]) - k);
						pnlty[i][j][k][t] = b + c;
					} else if (t == 1) {
						ind = pos[t][j + 1];
						ll a = max(0, get<0>(prefCnt[ind]) - i);
						ll b = max(0, get<1>(prefCnt[ind]) - j);
						ll c = max(0, get<2>(prefCnt[ind]) - k);
						pnlty[i][j][k][t] = a + c;
					} else {
						ind = pos[t][k + 1];
						ll a = max(0, get<0>(prefCnt[ind]) - i);
						ll b = max(0, get<1>(prefCnt[ind]) - j);
						ll c = max(0, get<2>(prefCnt[ind]) - k);
						pnlty[i][j][k][t] =  a + b;
					}
				}
			}
		}
	}

	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 t = 0; t < 3; t++) {
					for (int add = 0; add < 3; add++) {
						if (add == t) continue;
						ll cnt = dp[i][j][k][t] + pnlty[i][j][k][add];
						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;
      |              ^
joi2019_ho_t3.cpp:64:10: warning: unused variable 'a' [-Wunused-variable]
   64 |       ll a = max(0, get<0>(prefCnt[ind]) - i);
      |          ^
joi2019_ho_t3.cpp:71:10: warning: unused variable 'b' [-Wunused-variable]
   71 |       ll b = max(0, get<1>(prefCnt[ind]) - j);
      |          ^
joi2019_ho_t3.cpp:78:10: warning: unused variable 'c' [-Wunused-variable]
   78 |       ll c = max(0, get<2>(prefCnt[ind]) - k);
      |          ^

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