Submission #515781

#	Time	Username	Problem	Language	Result	Execution time	Memory
515781		thiago_bastos	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	753 ms	162912 KiB

joi2019_ho_t3

#include "bits/stdc++.h"

using namespace std;
 
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

const int N = 401, INF = 1e9;

int dp[N][N][N][3];

void solve() {
	
	int n, r, g, y;
	string s, p = "RGY";
	vector<int> pos[3];

	cin >> n >> s;

	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < 3; ++j) {
			if(s[i] == p[j])
				pos[j].push_back(i);
		}
	}

	r = pos[0].size();
	g = pos[1].size();
	y = pos[2].size();

	for(int i = 0; i <= r; ++i)
	for(int j = 0; j <= g; ++j)
	for(int k = 0; k <= y; ++k)
	for(int l = 0; l < 3; ++l)
		dp[i][j][k][l] = INF;

	for(int l = 0; l < 3; ++l) dp[0][0][0][l] = 0;

	for(int i = 0; i <= r; ++i) {
		for(int j = 0; j <= g; ++j) {
			for(int k = 0; k <= y; ++k) {
				int hi[3][2] = {{0}};

				if(i > 0) {
					int p = pos[0][i - 1];
					int& a = hi[0][0];
					int& b = hi[0][1];

					while(a < g && pos[1][a] < p) ++a;
					while(b < y && pos[2][b] < p) ++b;

					int moves = max(0, a - j) + max(0, b - k);

					for(int l : {1, 2})
						dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k][l] + moves);
				}

				if(j > 0) {
					int p = pos[1][j - 1];
					int& a = hi[1][0];
					int& b = hi[1][1];

					while(a < r && pos[0][a] < p) ++a;
					while(b < y && pos[2][b] < p) ++b;

					int moves = max(0, a - i) + max(0, b - k);

					for(int l : {0, 2})
						dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j - 1][k][l] + moves);
				}

				if(k > 0) {
					int p = pos[2][k - 1];
					int& a = hi[2][0];
					int& b = hi[2][1];

					while(a < r && pos[0][a] < p) ++a;
					while(b < g && pos[1][b] < p) ++b;

					int moves = max(0, a - i) + max(0, b - j);

					for(int l : {0, 1})
						dp[i][j][k][2] = min(dp[i][j][k][2], dp[i][j][k - 1][l] + moves);
				}
			}
		}
	}

	int ans = min({dp[r][g][y][0], dp[r][g][y][1], dp[r][g][y][2]});
	if(ans == INF) ans = -1;
	cout << ans << '\n';
}
 
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

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