This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#define FILE_IO
typedef pair<int, int> pii;
int N;
string s;
int getid(char ch)
{
if(ch == 'R') return 0;
if(ch == 'G') return 1;
if(ch == 'Y') return 2;
return -1;
}
int dp[405][405][405][3]; /// dp[r][g][y]
vector<int> pos[3];
int cost(int x, int y)
{
if(x < y) return 0;
return (x - y);
}
int main()
{
#ifdef FILE_IO
freopen("1.in", "r", stdin);
//freopen("1.out", "w", stdout);
#endif
cin >> N;
cin >> s;
for(int i = 0; i < N; i++)
pos[getid(s[i])].push_back(i + 1);
int R = pos[0].size(), G = pos[1].size(), Y = pos[2].size();
int mx = max({R, G, Y});
if(mx > (N + 1) / 2)
{
printf("-1\n");
exit(0);
}
for(int r = 0; r <= R; r++)
for(int g = 0; g <= G; g++)
for(int y = 0; y <= Y; y++)
{
int p = r + g + y;
if(p == 0) continue;
dp[r][g][y][0] = dp[r][g][y][1] = dp[r][g][y][2] = 1 << 30;
if(r > 0) dp[r][g][y][0] = min(dp[r - 1][g][y][1], dp[r - 1][g][y][2]) + cost(pos[0][r - 1], p);
if(g > 0) dp[r][g][y][1] = min(dp[r][g - 1][y][0], dp[r][g - 1][y][2]) + cost(pos[1][g - 1], p);
if(y > 0) dp[r][g][y][2] = min(dp[r][g][y - 1][0], dp[r][g][y - 1][1]) + cost(pos[2][y - 1], p);
}
int ans = min({ dp[R][G][Y][0], dp[R][G][Y][1], dp[R][G][Y][2] });
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |