#include <bits/stdc++.h>
using namespace std;
const long long MX=450,INF=1e9;
long long dp[MX][MX][MX][3];
long long rpr[MX],gpr[MX],ypr[MX];
vector < long long > inr,ing,iny;
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
string s;
long long n;
cin>>n>>s;
s="*"+s;
for(long long i=1;i<=n;i++)
{
rpr[i]=rpr[i-1];
if(s[i]=='R')
{
inr.push_back(i);
rpr[i]++;
}
gpr[i]=gpr[i-1];
if(s[i]=='G')
{
ing.push_back(i);
gpr[i]++;
}
ypr[i]=ypr[i-1];
if(s[i]=='Y')
{
iny.push_back(i);
ypr[i]++;
}
}
for(long long r=0;r<=inr.size();r++)
{
for(long long g=0;g<=ing.size();g++)
{
for(long long y=0;y<=iny.size();y++)
{
dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=INF;
if(r+g+y==0)
{
dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=0;
continue;
}
if(r!=0)
{
dp[r][g][y][0]=min(dp[r-1][g][y][1],dp[r-1][g][y][2])+max(0LL,gpr[inr[r-1]]-g)+max(0LL,ypr[inr[r-1]]-y);
}
if(g!=0)
{
dp[r][g][y][1]=min(dp[r][g-1][y][0],dp[r][g-1][y][2])+max(0LL,rpr[ing[g-1]]-r)+max(0LL,ypr[ing[g-1]]-y);
}
if(y!=0)
{
dp[r][g][y][2]=min(dp[r][g][y-1][0],dp[r][g][y-1][1])+max(0LL,rpr[iny[y-1]]-r)+max(0LL,gpr[iny[y-1]]-g);
}
}
}
}
long long ans=min({dp[inr.size()][ing.size()][iny.size()][0],dp[inr.size()][ing.size()][iny.size()][1],dp[inr.size()][ing.size()][iny.size()][2]});
cout<<((ans==INF)?-1:ans)<<"\n";
return 0;
}
Compilation message (stderr)
/tmp/ccf1znrO.o: in function `main':
joi2019_ho_t3.cpp:(.text.startup+0x32): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
joi2019_ho_t3.cpp:(.text.startup+0x51): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
joi2019_ho_t3.cpp:(.text.startup+0x4ff): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
/tmp/ccf1znrO.o: in function `_GLOBAL__sub_I_dp':
joi2019_ho_t3.cpp:(.text.startup+0x631): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
collect2: error: ld returned 1 exit status