oj.uz

Submission #208496

# Submission time Handle Problem Language Result Execution time Memory
208496 2020-03-11T10:54:23 Z Siberian Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 6392 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}

const int MAXN = 410;

int n;
int a[MAXN];

void read() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		char x;
		cin >> x;
		if (x == 'R') a[i] = 0;
		else if (x == 'G') a[i] = 1;
		else a[i] = 2;
	}
}

const int INF = 1e9 + 10;
int dp[MAXN][MAXN][3][3];

void build() {
	for (int l = 0; l < MAXN; l++)
		for (int r = 0; r < MAXN; r++)
			for (int chL = 0; chL < 3; chL++)
				for (int chR = 0; chR < 3; chR++)
					dp[l][r][chL][chR] = INF; 
}

void calc() {
	for (int r = 1; r <= n; r++) {
		for (int l = r; l >= 1; l--) {
			if (l == r) {
				dp[l][r][a[l]][a[l]] = 0;
				continue;
			}

			for (int chL = 0; chL < 3; chL++) {
				for (int chR = 0; chR < 3; chR++) {
					if (chL != a[r]) {
						chkmin(dp[l][r][a[r]][chR], dp[l][r - 1][chL][chR] + (r - l));
					}
					if (chR != a[l]) {
						chkmin(dp[l][r][chL][a[r]], dp[l + 1][r][chL][chR] + (r - l));
					}
				}
			}

			for (int chL = 0; chL < 3; chL++) {
				for (int chR = 0; chR < 3; chR++) {
					for (int mid = l; mid < r; mid++) {
						for (int chMid_L = 0; chMid_L < 3; chMid_L++) {
							for (int chMid_R = 0; chMid_R < 3; chMid_R++) {
								if (chMid_L == chMid_R) continue;
								chkmin(dp[l][r][chL][chR], dp[l][mid][chL][chMid_L] + dp[mid + 1][r][chMid_R][chR]);
							}
						}
					}
				}
			}
		}
	}
}

int ans;

void make_ans() {
	ans = INF;
	for (int chL = 0; chL < 3; chL++) {
		for (int chR = 0; chR < 3; chR++) {
			chkmin(ans, dp[1][n][chL][chR]);
		}
	}
	if (ans == INF) ans = -1;
}

void run() {
	build();
	calc();
	make_ans();
}

void write() {
	cout << ans << endl;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	write();
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 8 ms 6264 KB Output is correct
4 Incorrect 8 ms 6392 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 8 ms 6264 KB Output is correct
4 Incorrect 8 ms 6392 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Execution timed out 1080 ms 6264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6264 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 8 ms 6264 KB Output is correct
4 Incorrect 8 ms 6392 KB Output isn't correct
5 Halted 0 ms 0 KB -