oj.uz

Submission #820206

# Submission time Handle Problem Language Result Execution time Memory
820206 2023-08-11T01:16:05 Z Zanite Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 0 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;

array<int, 255> colorCode;
const int iINF	= 1e9;
const int maxN	= 423;

int N, cnt[3], color[maxN], pos[3][maxN], pf[3][maxN];
int dp[maxN][maxN][maxN][3];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	colorCode['R'] = 0;
	colorCode['G'] = 1;
	colorCode['Y'] = 2;

	cin >> N;
	char buf;
	for (int i = 1; i <= N; i++) {
		cin >> buf;
		color[i] = colorCode[buf];
	}

	#define R	cnt[0]
	#define G	cnt[1]
	#define Y	cnt[2]

	#define r	lpos[0]
	#define g	lpos[1]
	#define y	lpos[2]
	
	for (int i = 1; i <= N; i++) {
		pos[color[i]][++cnt[color[i]]] = i;
		for (int j = 0; j <= 2; j++) {
			pf[j][i] = pf[j][i-1] + (color[i] == j);
		}
	}

	int bound	= (N + 1) / 2;
	if (max({R, G, Y}) >= bound) {
		cout << -1 << '\n';
		return 0;
	}

	// dp[r][g][y][lst] = number of swaps to the left that must be done
	// to get r red, g green, and y yellow with last color lst
	array<int, 3> lpos;
	for (int n = 1; n <= N; n++) {
		for (r = 0; r <= bound; r++) {
			for (g = 0; g <= min(n-r, bound); g++) {
				y = n-r-g;
				for (int lst = 0; lst <= 2; lst++) {
					if (!lpos[lst]) {
						dp[r][g][y][lst] = iINF;
						continue;
					}

					int prv = iINF;
					lpos[lst]--;
					for (int plst = 0; plst <= 2; plst++) {
						if (plst == lst) continue;
						prv = min(prv, dp[r][g][y][plst]);
					}
					lpos[lst]++;

					int swaps = 0;
					for (int i = 0; i <= 2; i++) {
						if (i == lst) continue;
						swaps += max(0, pf[i][pos[lst][lpos[lst]]] - lpos[i]);
					}

					dp[r][g][y][lst] = min(iINF, prv + swaps);
				}
			}
		}
	}

	int ans = iINF;
	for (int lst = 0; lst <= 2; lst++) ans = min(ans, dp[R][G][Y][lst]);
	if (ans == iINF) ans = -1;
	cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -