#include <bits/stdc++.h>
using namespace std;
long long dp[3][401][401][401];
vector<int>col[3];
long long pref[3][401];
long long solve(int la,int r,int g,int b){
if(r+1==col[0].size()&&g+1==col[1].size()&&b+1==col[2].size()){
return 0;
}
if(dp[la][r][g][b]!=-1)return dp[la][r][g][b];
long long c1 = 1e18;
for(int ne = 0;ne<3;ne++){
if(ne==la)continue;
if((ne==0&&r+1==col[0].size())||(ne==1&&g+1==col[1].size())||(ne==2&&b+1==col[2].size()))continue;
int p1 = 0 , p2 = 0 , p3 = 0 , dif;
if(ne==0)p1 = col[ne][r+1];
if(ne==1)p1 = col[ne][g+1];
if(ne==2)p1 = col[ne][b+1];
if(la==0)p2 = col[la][r];
if(la==1)p2 = col[la][g];
if(la==2)p2 = col[la][b];
if(ne!=0&&la!=0){p3 = col[0][r];dif = 0;}
if(ne!=1&&la!=1){p3 = col[1][g];dif = 1;}
if(ne!=2&&la!=2){p3 = col[2][b];dif = 2;}
long long ans = max(0LL,pref[la][p1]-pref[la][p2])+max(0LL,pref[dif][p1]-pref[dif][p3]);
if(ne==0)c1 = min(c1,solve(ne,r+1,g,b)+ans);
if(ne==1)c1 = min(c1,solve(ne,r,g+1,b)+ans);
if(ne==2)c1 = min(c1,solve(ne,r,g,b+1)+ans);
}
return dp[la][r][g][b] =c1;
}
signed main(){
int len;cin>>len;
string s;cin>>s;
s = 'a'+s;
col[0].push_back(0);col[1].push_back(0);col[2].push_back(0);
memset(pref,0,sizeof pref);
for(int i = 1;i<s.size();i++){
pref[0][i]+=pref[0][i-1];
pref[1][i]+=pref[1][i-1];
pref[2][i]+=pref[2][i-1];
if(s[i]=='R'){col[0].push_back(i);pref[0][i]++;}
if(s[i]=='G'){col[1].push_back(i);pref[1][i]++;}
if(s[i]=='Y'){col[2].push_back(i);pref[2][i]++;}
}
memset(dp,-1,sizeof dp);
cout<<min({solve(0,0,0,0),solve(1,0,0,0),solve(2,0,0,0)});
}
Compilation message
joi2019_ho_t3.cpp: In function 'long long int solve(int, int, int, int)':
joi2019_ho_t3.cpp:8:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | if(r+1==col[0].size()&&g+1==col[1].size()&&b+1==col[2].size()){
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | if(r+1==col[0].size()&&g+1==col[1].size()&&b+1==col[2].size()){
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:8:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | if(r+1==col[0].size()&&g+1==col[1].size()&&b+1==col[2].size()){
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | if((ne==0&&r+1==col[0].size())||(ne==1&&g+1==col[1].size())||(ne==2&&b+1==col[2].size()))continue;
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:15:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | if((ne==0&&r+1==col[0].size())||(ne==1&&g+1==col[1].size())||(ne==2&&b+1==col[2].size()))continue;
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:15:81: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | if((ne==0&&r+1==col[0].size())||(ne==1&&g+1==col[1].size())||(ne==2&&b+1==col[2].size()))continue;
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 1;i<s.size();i++){
| ~^~~~~~~~~
joi2019_ho_t3.cpp: In function 'long long int solve(int, int, int, int)':
joi2019_ho_t3.cpp:26:94: warning: 'dif' may be used uninitialized in this function [-Wmaybe-uninitialized]
26 | long long ans = max(0LL,pref[la][p1]-pref[la][p2])+max(0LL,pref[dif][p1]-pref[dif][p3]);
| ~~~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
419 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
419 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
392 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
419 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
