#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
vector <int> v[3];
int dp[410][410][410][3];
char s[430];
int calcul (int nr0 , int nr1 , int nr2 , int curr){
int poz , st , dr , mid;
if (curr == 0)
curr = v[0][nr0];
else if (curr == 1)
curr = v[1][nr1];
else curr = v[2][nr2];
/// curr e poz initiala
poz = curr;
if (!v[0].empty()){
st = 0;
dr = nr0 - 1;
while (st <= dr){
mid = (st + dr) / 2;
if (v[0][mid] <= curr)
st = mid + 1;
else dr = mid - 1;
}
poz += (nr0 - st); /// st = primul mai mare decat curr
}
if (!v[1].empty()){
st = 0;
dr = nr1 - 1;
while (st <= dr){
mid = (st + dr) / 2;
if (v[1][mid] <= curr)
st = mid + 1;
else dr = mid - 1;
}
poz += (nr1 - st); /// st = primul mai mare decat curr
}
if (!v[2].empty()){
st = 0;
dr = nr2 - 1;
while (st <= dr){
mid = (st + dr) / 2;
if (v[2][mid] <= curr)
st = mid + 1;
else dr = mid - 1;
}
poz += (nr2 - st); /// st = primul mai mare decat curr
}
return poz - (nr0 + nr1 + nr2 + 1);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , i , sum , j , k , sol;
fscanf (fin,"%d\n",&n);
fgets (s + 1 , 420 , fin); /// hehe
for (i = n ; i ; i--){
if (s[i] == 'R'){
v[0].push_back(i);
}
else if (s[i] == 'G'){
v[1].push_back(i);
}
else {
v[2].push_back(i);
}
}
reverse(v[0].begin() , v[0].end());
reverse(v[1].begin() , v[1].end());
reverse(v[2].begin() , v[2].end());
/// dp[i][j][k][0 / 1 / 2] = i 0 , j 1 , k 2 , current e 0 / 1 / 2
for (sum = 1 ; sum <= n ; sum++){
for (i = 0 ; i <= v[0].size() ; i++){
for (j = 0 ; j <= v[1].size() && i + j <= sum ; j++){
k = sum - i - j;
if (k >= 0 && k <= v[2].size()){
dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = INF;
}
}
}
}
if (!v[0].empty())
dp[1][0][0][0] = v[0][0] - 1;
if (!v[1].empty())
dp[0][1][0][1] = v[1][0] - 1;
if (!v[2].empty())
dp[0][0][1][2] = v[2][0] - 1;
/// initializari
sol = 2000000000;
for (sum = 2 ; sum <= n ; sum++){
for (i = 0 ; i <= v[0].size() ; i++){
for (j = 0 ; j <= v[1].size() && i + j <= sum ; j++){
k = sum - i - j;
if (k < 0 || k > v[2].size())
continue;
/// acum calculezi propriu zis
if (i){ /// incerci sa pui 0
dp[i][j][k][0] = min(dp[i - 1][j][k][1] , dp[i - 1][j][k][2]) + calcul(i - 1 , j , k , 0);
}
if (j){ /// incerci sa pui 1
dp[i][j][k][1] = min(dp[i][j - 1][k][0] , dp[i][j - 1][k][2]) + calcul(i , j - 1 , k , 1);
}
if (k){ /// incerci sa pui 2
dp[i][j][k][2] = min(dp[i][j][k - 1][0] , dp[i][j][k - 1][1]) + calcul(i , j , k - 1 , 2);
}
if (sum == n){
sol = min( min(sol , dp[i][j][k][0]) , min(dp[i][j][k][1] , dp[i][j][k][2]) );
}
}
}
}
if (sol == INF)
sol = -1;
fprintf (fout,"%d",sol);
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:96:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i <= v[0].size() ; i++){
~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:98:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0 ; j <= v[1].size() && i + j <= sum ; j++){
~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:101:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (k >= 0 && k <= v[2].size()){
~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:126:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i <= v[0].size() ; i++){
~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:128:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0 ; j <= v[1].size() && i + j <= sum ; j++){
~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:131:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (k < 0 || k > v[2].size())
~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:71:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d\n",&n);
~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:72:11: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fgets (s + 1 , 420 , fin); /// hehe
~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
93 ms |
163064 KB |
Output is correct |
| 3 |
Correct |
111 ms |
162180 KB |
Output is correct |
| 4 |
Correct |
97 ms |
163064 KB |
Output is correct |
| 5 |
Correct |
92 ms |
163064 KB |
Output is correct |
| 6 |
Correct |
102 ms |
163064 KB |
Output is correct |
| 7 |
Correct |
94 ms |
162168 KB |
Output is correct |
| 8 |
Correct |
101 ms |
162168 KB |
Output is correct |
| 9 |
Correct |
94 ms |
161400 KB |
Output is correct |
| 10 |
Correct |
98 ms |
163064 KB |
Output is correct |
| 11 |
Correct |
101 ms |
163064 KB |
Output is correct |
| 12 |
Correct |
28 ms |
44032 KB |
Output is correct |
| 13 |
Correct |
47 ms |
77176 KB |
Output is correct |
| 14 |
Correct |
64 ms |
111352 KB |
Output is correct |
| 15 |
Correct |
94 ms |
162936 KB |
Output is correct |
| 16 |
Correct |
100 ms |
163064 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
