#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[N][N][N][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()){
cev=min(cev,hesap(r+1,g,y,0,sira+1)+red[r]+((g>0)?tut[0][1][r][g-1]:0) +((y>0)?tut[0][2][r][y-1]:0)-sira);
}
if(son!=1&&g<green.size()){
cev=min(cev,hesap(r,g+1,y,1,sira+1)+green[g]+((r>0)?tut[1][0][g][r-1]:0 )+((y>0)?tut[1][2][g][y-1]:0)-sira);
}
if(son!=2&&y<yellow.size()){
cev=min(cev,hesap(r,g,y+1,2,sira+1)+yellow[y]+((r>0)?tut[2][0][y][r-1]:0) +((g>0)?tut[2][1][y][g-1]:0)-sira);
}
//cout<<cev<<" "<<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:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | if(son!=1&&g<green.size()){
| ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | if(son!=2&&y<yellow.size()){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=0;i<red.size();i++){
| ~^~~~~~~~~~~
joi2019_ho_t3.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int j=0;j<green.size();j++){
| ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0;i<red.size();i++){
| ~^~~~~~~~~~~
joi2019_ho_t3.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int j=0;j<yellow.size();j++){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:56:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=0;i<green.size();i++){
| ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int j=0;j<red.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<yellow.size();j++){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i=0;i<yellow.size();i++){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int j=0;j<red.size();j++){
| ~^~~~~~~~~~~
joi2019_ho_t3.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i=0;i<yellow.size();i++){
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:82:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int j=0;j<green.size();j++){
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
367 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
367 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
303 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
367 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
