#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//#define endl "\n"
#define ll long long
#define pb push_back
#define N 405
int n;
vector<int> red,green,yellow;
ll int tut[3][3][N][N];
ll int dp[3][3][3][3];
ll int hesap(int r,int g,int y,int son,int sira){
if(sira>=n)return 0;
if(dp[r][g][y][son]!=-1)return dp[r][g][y][son];
ll int cev=1000000000;
if((son!=0||r+g+y==0)&&r<red.size()){
//cout<<cev<<" a "<<r<<" "<<g<<" "<<y<<endl;
cev=min(cev,hesap(r+1,g,y,0,sira+1)+red[r]+tut[0][1][r][g-1]+tut[0][2][r][y-1]-sira);
}
if(son!=1&&g<green.size()){
//cout<<cev<<" b "<<r<<" "<<g<<" "<<y<<endl;
cev=min(cev,hesap(r,g+1,y,1,sira+1)+green[g]+tut[1][0][g][r-1]+tut[1][2][g][y-1]-sira);
}
if(son!=2&&y<yellow.size()){
//cout<<cev<<" c "<<r<<" "<<g<<" "<<y<<endl;
cev=min(cev,hesap(r,g,y+1,2,sira+1)+yellow[y]+tut[2][0][y][r-1]+tut[2][1][y][g-1]-sira);
}
//cout<<cev<<endl;
//cout<<r<<" "<<g<<" "<<y<<" "<<son<<" "<<sira<<endl;
return dp[r][g][y][son]=cev;
}
int arr[N];
int main(){
lalala;
memset(dp,-1,sizeof(dp));
cin>>n;
string str;cin>>str;
for(int i=0;i<n;i++){
if(str[i]=='G')green.pb(i);
if(str[i]=='R')red.pb(i);
if(str[i]=='Y')yellow.pb(i);
}
for(int i=0;i<red.size();i++){
int kac=0;
for(int j=0;j<green.size();j++){
if(red[i]<green[j]){
kac++;
tut[0][1][i][j]=kac;
}
}
}
for(int i=0;i<red.size();i++){
int kac=0;
for(int j=0;j<yellow.size();j++){
if(red[i]<yellow[j]){
kac++;
tut[0][2][i][j]=kac;
}
}
}
for(int i=0;i<green.size();i++){
int kac=0;
for(int j=0;j<red.size();j++){
if(green[i]<red[j]){
kac++;
tut[1][0][i][j]=kac;
}
}
}
for(int i=0;i<green.size();i++){
int kac=0;
for(int j=0;j<yellow.size();j++){
if(green[i]<yellow[j]){
kac++;
tut[1][2][i][j]=kac;
}
}
}
for(int i=0;i<yellow.size();i++){
int kac=0;
for(int j=0;j<red.size();j++){
if(yellow[i]<red[j]){
kac++;
tut[2][0][i][j]=kac;
}
}
}
for(int i=0;i<yellow.size();i++){
int kac=0;
for(int j=0;j<green.size();j++){
if(yellow[i]<green[j]){
kac++;
tut[2][1][i][j]=kac;
}
}
}
ll int a=hesap(0,0,0,0,0);
if(a>=1000000000)a=-1;
cout<<a<<endl;
}
Compilation message
joi2019_ho_t3.cpp: In function 'long long int hesap(int, int, int, int, int)':
joi2019_ho_t3.cpp:16:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | if((son!=0||r+g+y==0)&&r<red.size()){
| ~^~~~~~~~~~~
joi2019_ho_t3.cpp:20:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | if(son!=1&&g<green.size()){
| ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | if(son!=2&&y<yellow.size()){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<red.size();i++){
| ~^~~~~~~~~~~
joi2019_ho_t3.cpp:48:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int j=0;j<green.size();j++){
| ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<red.size();i++){
| ~^~~~~~~~~~~
joi2019_ho_t3.cpp:57:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int j=0;j<yellow.size();j++){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i=0;i<green.size();i++){
| ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int j=0;j<red.size();j++){
| ~^~~~~~~~~~~
joi2019_ho_t3.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i=0;i<green.size();i++){
| ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int j=0;j<yellow.size();j++){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i=0;i<yellow.size();i++){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int j=0;j<red.size();j++){
| ~^~~~~~~~~~~
joi2019_ho_t3.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=0;i<yellow.size();i++){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int j=0;j<green.size();j++){
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
324 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
324 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
324 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
