#include<bits/stdc++.h>
/*
#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
*/
//01001101 01100001 01101011 01101000 01100001 01100111 01100001 01111001
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define sz(a) a.size()
#define nl '\n'
#define popb pop_back()
#define ld double
#define ull unsigned long long
#define ff first
#define ss second
#define fix fixed << setprecision
#define pii pair<int, int>
#define E exit (0)
#define int long long
const int inf = 1e15, N = 1500, mod = 998244353;
vector<pii> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int cnt[N][3];
vector<int> pos[3];
main() {
//freopen("triangles.in", "r", stdin);
//freopen("triangles.out", "w", stdout);
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
int n;
cin >> n;
string s;
cin >> s;
for (int i = 1; i <= n; i++) {
cnt[i][0] = cnt[i - 1][0];
cnt[i][1] = cnt[i - 1][1];
cnt[i][2] = cnt[i - 1][2];
if (s[i - 1] == 'R') {
cnt[i][0]++;
pos[0].pb(i);
}
if (s[i - 1] == 'G') {
cnt[i][1]++;
pos[1].pb(i);
}
if (s[i - 1] == 'Y') {
cnt[i][2]++;
pos[2].pb(i);
}
}
if (cnt[n][0] > cnt[n][1] + cnt[n][2] + 1) cout << -1, E;
if (cnt[n][1] > cnt[n][0] + cnt[n][2] + 1) cout << -1, E;
if (cnt[n][2] > cnt[n][1] + cnt[n][2] + 1) cout << -1, E;
int dp[cnt[n][0] + 1][cnt[n][1] + 1][cnt[n][2] + 1][3];
dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
for (int i = 0; i <= cnt[n][0]; i++) {
for (int j = 0; j <= cnt[n][1]; j++) {
for (int k = 0; k <= cnt[n][2]; k++) {
if (!i && !j && !k) continue;
int len = i + j + k;
if (!i) dp[i][j][k][0] = inf;
else {
int p = pos[0][i - 1];
p += max(0ll, j - cnt[p][1]) + max(0ll, k - cnt[p][2]);
dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + p - len;
}
if (!j) dp[i][j][k][1] = inf;
else {
int p = pos[1][j - 1];
p += max(0ll, i - cnt[p][0]) + max(0ll, k - cnt[p][2]);
dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + p - len;
}
if (!k) dp[i][j][k][2] = inf;
else {
int p = pos[2][k - 1];
p += max(0ll, j - cnt[p][1]) + max(0ll, i - cnt[p][0]);
dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + p - len;
}
}
}
}
cout << min(dp[cnt[n][0]][cnt[n][1]][cnt[n][2]][0], min(dp[cnt[n][0]][cnt[n][1]][cnt[n][2]][1], dp[cnt[n][0]][cnt[n][1]][cnt[n][2]][2]));
}
Compilation message
joi2019_ho_t3.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
39 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
252 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
252 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1228 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1228 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1228 KB |
Output is correct |
| 12 |
Correct |
1 ms |
460 KB |
Output is correct |
| 13 |
Correct |
1 ms |
716 KB |
Output is correct |
| 14 |
Correct |
1 ms |
972 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
252 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
