#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 405;
vector<int> red, yellow, green;
int pref[3][N];
int sum(int idx_from, int to, int from) {
if(from < to)
return 0;
return pref[idx_from][from] - pref[idx_from][to];
}
void Solve() {
int n;
cin >> n;
string s;
cin >> s;
int red_cnt = 0, yellow_cnt = 0, green_cnt = 0;
pref[0][0] = 0;
pref[1][0] = 0;
pref[2][0] = 0;
red.push_back(0);
yellow.push_back(0);
green.push_back(0);
for(int i = 0; i < s.size(); i++) {
if(s[i] == 'R') {
red_cnt++;
red.push_back(i);
pref[0][i]++;
}
else if(s[i] == 'Y') {
yellow_cnt++;
yellow.push_back(i);
pref[1][i]++;
}
else {
green_cnt++;
green.push_back(i);
pref[2][i]++;
}
if(i != 0) {
pref[0][i] += pref[0][i - 1];
pref[1][i] += pref[1][i - 1];
pref[2][i] += pref[2][i - 1];
}
}
int dp[red_cnt + 1][yellow_cnt + 1][green_cnt + 1][3];
for(int i = 0; i <= red_cnt; i++) {
for(int j = 0; j <= yellow_cnt; j++) {
for(int k = 0; k <= green_cnt; k++) {
for(int l = 0; l < 3; l++) {
dp[i][j][k][l] = INT_MAX;
}
}
}
}
for(int l = 0; l < 3; l++) {
dp[0][0][0][l] = 0;
}
for(int i = 0; i <= red_cnt; i++) {
for(int j = 0; j <= yellow_cnt; j++) {
for(int k = 0; k <= green_cnt; k++) {
if(i == 0 && j == 0 && k == 0)
continue;
for(int cur = 0; cur < 3; cur++) {
for(int last = 0; last < 3; last++) {
if(cur == last)
continue;
if(cur == 0) {
if(i == 0)
continue;
dp[i][j][k][cur] = min(dp[i][j][k][cur], dp[i - 1][j][k][last] + sum(1, yellow[j], red[i]) + sum(2, green[k], red[i]));
}
else if(cur == 1) {
if(j == 0)
continue;
dp[i][j][k][cur] = min(dp[i][j][k][cur], dp[i][j - 1][k][last] + sum(0, red[i], yellow[j]) + sum(2, green[k], yellow[j]));
}
else {
if(k == 0)
continue;
dp[i][j][k][cur] = min(dp[i][j][k][cur], dp[i][j][k - 1][last] + sum(0, red[i], green[k]) + sum(1, yellow[j], green[k]));
}
}
}
}
}
}
int ans = min(dp[red_cnt][yellow_cnt][green_cnt][0], min(dp[red_cnt][yellow_cnt][green_cnt][1], dp[red_cnt][yellow_cnt][green_cnt][2]));
for(int i = 0; i <= red_cnt; i++) {
for(int j = 0; j <= yellow_cnt; j++) {
for(int k = 0; k <= green_cnt; k++) {
for(int l = 0; l < 3; l++) {
cout << dp[i][j][k][l] << " ";
}
}
}
}
if(ans >= 1e7) {
cout << "-1\n";
}
else {
cout << ans << "\n";
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Solve();
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In function 'void Solve()':
joi2019_ho_t3.cpp:27:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
