#include <bits/stdc++.h>
#define MAX 405
///Uma dp meio complicadinha
///A ideia eh a seguinte:
///1-> Quantos valores azuis restam
///2-> Quantos valores vermelhos restam
///3-> Quantos valores verdes restam
///4-> (Para remover) coordenada atual
///Por enquanto sera O(N^4), mas poderemos otimizar depois
bool existe[100000000];
int tab[100000000];
std::vector<int> cords[3];
int N;
int array[MAX]={};
int getval(char ch){
if(ch=='R')return 0;else if(ch=='G')return 1;return 2;
}
int geracord(int a,int b,int c,int d,int e){
int bonus = 1;
int base = e*bonus;
bonus*=5;
base+=d*bonus;
bonus*=cords[1].size()+1;
base+=c*bonus;
bonus*=cords[2].size()+1;
base+=b*bonus;
bonus*=cords[0].size()+1;
base+=a*bonus;
return base;
}
int proximo(int red,int blue,int green){
int min=N;
if(red!=cords[0].size())min=std::min(min,cords[0][red]);
if(green!=cords[1].size())min=std::min(min,cords[1][green]);
if(blue!=cords[2].size())min=std::min(min,cords[2][blue]);
return min;
}
int pref[3][405][405];
int dp(int val,int red,int blue,int green,int last){
if(red+blue+green==N)return 0;
int pos=0;
{
int arr[]={red,green,blue};
pos=cords[val][arr[val]];
}
int cordcomp=geracord(val,red,blue,green,last);
if(existe[cordcomp])return tab[cordcomp];
existe[cordcomp]=true;
///Prossegue com o valor
int ans=1e9;
if(array[pos]!=last){
switch(array[pos]){
case 0:
ans=dp(array[proximo(red+1,blue,green)],red+1,blue,green,array[pos]);break;
case 1:
ans=dp(array[proximo(red,blue,green+1)],red,blue,green+1,array[pos]);break;
case 2:
ans=dp(array[proximo(red,blue+1,green)],red,blue+1,green,array[pos]);break;
}
}
///O valor da distancia estah INCORRETO, como melhorar a conta?
///Faz a troca magica
if(last!=0&&red!=cords[0].size()&&array[pos]!=0){
int truecusto=0;
int destino = cords[0][red];
truecusto+=pref[0][red][destino];
if(pos)truecusto-=pref[0][red][pos-1];
truecusto+=pref[1][green][destino];
if(pos)truecusto-=pref[1][green][pos-1];
truecusto+=pref[2][blue][destino];
if(pos)truecusto-=pref[2][blue][pos-1];
ans=std::min(ans,cords[0][red]-pos-truecusto + (dp(val,red+1,blue,green,0)));
}
if(last!=1&&green!=cords[1].size()&&array[pos]!=1){
int truecusto=0;
int destino = cords[1][green];
truecusto+=pref[0][red][destino];
if(pos)truecusto-=pref[0][red][pos-1];
truecusto+=pref[1][green][destino];
if(pos)truecusto-=pref[1][green][pos-1];
truecusto+=pref[2][blue][destino];
if(pos)truecusto-=pref[2][blue][pos-1];
ans=std::min(ans,cords[1][green]-pos-truecusto + (dp(val,red,blue,green+1,1)));
}
if(last!=2&&blue!=cords[2].size()&&array[pos]!=2){
int truecusto=0;
int destino = cords[2][blue];
truecusto+=pref[0][red][destino];
if(pos)truecusto-=pref[0][red][pos-1];
truecusto+=pref[1][green][destino];
if(pos)truecusto-=pref[1][green][pos-1];
truecusto+=pref[2][blue][destino];
if(pos)truecusto-=pref[2][blue][pos-1];
ans=std::min(ans,cords[2][blue]-pos-truecusto + (dp(val,red,blue+1,green,2)));
}
return tab[cordcomp]=ans;
}
int main()
{
std::cin>>N;
std::string s;
std::cin>>s;
for(int i=0;i!=s.size();++i){
int u = getval(s[i]);
cords[u].push_back(i);
array[i]=u;
}
{
for(int j=0;j!=3;++j){
for(int i=0;i!=cords[j].size();++i){
for(int k=0;k<i;++k){
pref[j][i][cords[j][k]]++;
}
for(int k=1;k!=MAX;++k){
pref[j][i][k]+=pref[j][i][k-1];
}
}
}
}
int ans=dp(array[0],0,0,0,3);
if(ans==1e9)ans=-1;
std::cout<<ans<<"\n";
}
Compilation message
joi2019_ho_t3.cpp: In function 'int proximo(int, int, int)':
joi2019_ho_t3.cpp:33:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if(red!=cords[0].size())min=std::min(min,cords[0][red]);
| ~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:34:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if(green!=cords[1].size())min=std::min(min,cords[1][green]);
| ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:35:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if(blue!=cords[2].size())min=std::min(min,cords[2][blue]);
| ~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int dp(int, int, int, int, int)':
joi2019_ho_t3.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if(last!=0&&red!=cords[0].size()&&array[pos]!=0){
| ~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(last!=1&&green!=cords[1].size()&&array[pos]!=1){
| ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | if(last!=2&&blue!=cords[2].size()&&array[pos]!=2){
| ~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i=0;i!=s.size();++i){
| ~^~~~~~~~~~
joi2019_ho_t3.cpp:122:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int i=0;i!=cords[j].size();++i){
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1876 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2004 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2148 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2004 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2004 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2004 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 12 |
Correct |
1 ms |
980 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1568 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
