#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SREP(i, a, b) for(ll i = a; i < b; i++)
#define NREP(i, a, b) for(ll i = a; i <= b; i++)
int main() {
ll N, R = 0, Y = 0, G = 0; string S; cin >> N >> S;
vector<ll> Rpos, Ypos, Gpos;
SREP(i, 0, N) {
if(S[i] == 'R') {
Rpos.push_back(i); R++;
} else if(S[i] == 'Y') {
Ypos.push_back(i); Y++;
} else {
Gpos.push_back(i); G++;
}
}
ll dp[R + 1][Y + 1][G + 1][3];
NREP(i, 0, R) NREP(j, 0, Y) NREP(k, 0, G) SREP(l, 0, 3) dp[i][j][k][l] = 1e18;
SREP(i, 0, 3) dp[0][0][0][i] = 0;
NREP(i, 0, R) NREP(j, 0, Y) NREP(k, 0, G) {
if(i != 0) dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + abs(Rpos[i - 1] - (i + j + k - 1));
if(j != 0) dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + abs(Ypos[j - 1] - (i + j + k - 1));
if(k != 0) dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + abs(Gpos[k - 1] - (i + j + k - 1));
}
ll ans = LONG_LONG_MAX;
SREP(i, 0, 3) ans = min(ans, dp[R][Y][G][i]);
if(ans < 1e18) cout << ans/2;
else cout << "-1";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
0 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
300 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
0 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
300 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1196 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
724 KB |
Output is correct |
| 14 |
Correct |
1 ms |
852 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1236 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
0 ms |
296 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
300 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
