Submission #909798

#	Time	Username	Problem	Language	Result	Execution time	Memory
909798		OAleksa	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	99 ms	465396 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 410;
const int inf = 1e9 + 69;
int dp[N][N][N][3], n, pr[3][N];
string s;
vector<int> pos[3];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> s;
  	int a = 0, b = 0, c = 0;
  	for (int i = 0;i < n;i++) {
  		if (s[i] == 'R')
  			s[i] = 'A';
  		else if (s[i] == 'G')
  			s[i] = 'B';
  		else
  			s[i] = 'C';
  		a += (s[i] == 'A');
  		b += (s[i] == 'B');
  		c += (s[i] == 'C');
  		pos[s[i] - 'A'].push_back(i);
  	}
  	for (int i = 0;i < n;i++) {
  		if (i > 0) {
				pr[0][i] += pr[0][i - 1];
  			pr[1][i] += pr[1][i - 1];
  			pr[2][i] += pr[2][i - 1]; 
  		}
  		pr[0][i] += (s[i] == 'A');
  		pr[1][i] += (s[i] == 'B');
  		pr[2][i] += (s[i] == 'C');
  	}
  	for (int i = 0;i <= a;i++) {
  		for (int j = 0;j <= b;j++) {
  			for (int k = 0;k <= c;k++)
  				dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = inf;
  		}
  	}
  	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
  	auto C = [&](int L, int R) {
  		if (L == 0)
  			return pr[2][R];
  		else if (R < L)
  			return 0ll;
  		return pr[2][R] - pr[2][L - 1];
  	};
  	auto B = [&](int L, int R) {
  		if (L == 0)
  			return pr[1][R];
  		else if (R < L)
  			return 0ll;
  		return pr[1][R] - pr[1][L - 1];
  	};
  	auto A = [&](int L, int R) {
  		if (L == 0)
  			return pr[0][R];
  		else if (R < L)
  			return 0ll;
  		return pr[0][R] - pr[0][L - 1];
  	};
  	for (int i = 0;i <= a;i++) {
  		for (int j = 0;j <= b;j++) {
  			for (int k = 0;k <= c;k++) {
  				int p = i + j + k - 1;
  				if (i > 0) {
  					int L = p, R = pos[0][i - 1];
  					int p1 = 0, p2 = 0;
  					if (j > 0)
  						p1 = pos[1][j - 1];
  					if (k > 0)
  						p2 = pos[2][k - 1];
  					if (R <= L)
  						dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]);
  					else
  						dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + (R + C(R, p2) + B(R, p1) - L);
  				}
  				if (j > 0) {
  					int L = p, R = pos[1][j - 1];
  					int p1 = 0, p2 = 0;
  					if (i > 0)
  						p1 = pos[0][i - 1];
  					if (k > 0)
  						p2 = pos[2][k - 1];
  					if (R <= L)
  						dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]);
  					else
  						dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + (R + A(R, p1) + C(R, p2) - L);
  				}
  				if (k > 0) {
  					int L = p, R = pos[2][k - 1];
  					int p1 = 0, p2 = 0;
  					if (i > 0)
  						p1 = pos[0][i - 1];
  					if (j > 0)
  						p2 = pos[1][j - 1];
  					if (R <= L)
  						dp[i][j][k][2] = min(dp[i][j][k - 1][1], dp[i][j][k - 1][0]);
  					else
  						dp[i][j][k][2] = min(dp[i][j][k - 1][1], dp[i][j][k - 1][0]) + (R + A(R, p1) + B(R, p2) - L);
  				}
  			}
  		}
  	}
  	int ans = inf;
  	for (int i = 0;i < 3;i++)
  		ans = min(ans, dp[a][b][c][i]);
  	if (ans >= inf)	
  		ans = -1;
  	cout << ans;
	}
  return 0;
}

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