Submission #444205

#	Time	Username	Problem	Language	Result	Execution time	Memory
444205		nonsensenonsense1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	497 ms	757620 KiB

joi2019_ho_t3

#include <cstdio>
#include <algorithm>
#include <cstring>

const int INF = 0x3f3f3f3f;

const int N = 401;
int n, amt[3], pos[3][N], pr[3][N], d[N][N][N][3];
char s[N];

int f(int last) 
{
	int &cur = d[amt[0]][amt[1]][amt[2]][last];
	if (cur == -1) {
		cur = INF;
		if (!(amt[0] + amt[1] + amt[2])) cur = 0;
		else for (int i = 0; i < 3; ++i) if (i != last && amt[i]) {
			--amt[i];
			int inc = 0;
			for (int j = 0; j < 3; ++j) if (j != i) inc += std::max(0, pr[j][pos[i][amt[i]]] - amt[j]);
			cur = std::min(cur, f(i) + inc);
			++amt[i];
		}
	}
	return cur;
}

int main() 
{
	memset(***d, -1, N * N * N * 3 << 2);
	scanf("%d%s", &n, s);
	for (int i = 0; i < n; ++i) {
		int cur;
		if (s[i] == 'R') cur = 0;
		else if (s[i] == 'G') cur = 1;
		else cur = 2;
		pos[cur][amt[cur]++] = i;
		for (int j = 0; j < 3; ++j) {
			pr[j][i] += cur == j;
			if (i) pr[j][i] += pr[j][i - 1];
		}
	}
	int ans = INF;
	for (int i = 0; i < 3; ++i) ans = std::min(ans, f(i));
	if (ans == INF) printf("-1\n");
	else printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%s", &n, s);
      |  ~~~~~^~~~~~~~~~~~~~~

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