Submission #909748

#	Time	Username	Problem	Language	Result	Execution time	Memory
909748		OAleksa	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	100 ms	307084 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;
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 <= 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;
  	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) {
  					dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + abs(pos[0][i - 1] - p);
  				}
  				if (j > 0) {
  					dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + abs(pos[1][j - 1] - p);
  				}
  				if (k > 0) {
  					dp[i][j][k][2] = min(dp[i][j][k - 1][1], dp[i][j][k - 1][0]) + abs(pos[2][k - 1] - p);
  				}
  			}
  		}
  	}
  	int ans = inf;
  	for (int i = 0;i < 3;i++)
  		ans = min(ans, dp[a][b][c][i]);
  	if (ans >= inf)	
  		ans = -2;
  	cout << ans / 2;
	}
  return 0;
}

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