| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1181735 | Szymon_Pilipczuk | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int sa[401];
int sb[401];
int sc[401];
int fa[400];
int fb[400];
int fc[400];
int dp[401][400][400][3];
int main()
{
int n;
cin>>n;
string s;
cin>>s;
int a = 0,b = 0,c =0;
for(int i = 0;i<n;i++)
{
sa[i+1] = sa[i];
sb[i+1] = sb[i];
sc[i+1] = sc[i];
if(s[i] == 'R')
{
sa[i+1]++;
fa[a] = i;
a++;
}
else if(s[i] == 'G')
{
sb[i+1]++;
fb[b] = i;
b++;
}
else
{
sc[i+1]++;
fc[c] = i;
c++;
}
}
for(int i = 0;i<=n;i++)
{
for(int j =0 ;j<n;j++)
{
for(int q =0 ;q<n;q++)
{
for(int r = 0;r<3;r++)
{
if(i == 0) dp[i][j][q][r] = 0;
else dp[i][j][q][r] = 1e9;
}
}
}
}
for(int i = 1;i<=n;i++)
{
for(int j = 0;j<=n;j++)
{
for(int q = 0;q<=n;q++)
{
if(i-j-q > sa[n] || j > sb[n] || q > sc[n] || j+q > i) continue;
for(int r = 0;r<3;r++)
{
if(i-j-q == 0 && r == 0) continue;
if(j == 0 && r == 1)continue;
if(q == 0 && r== 2) continue;
if(i-j-q != 0 && r == 0)dp[i][j][q][r] = min(dp[i-1][j][q][(r+1)%3],dp[i-1][j][q][(r+2)%3])+max(0,sb[fa[i-1-j-q]]-j)+max(0,sc[fa[i-1-j-q]]-q);
//(i == 4&&j == 1&&q == 1&& r == 1) cout<<dp[i][j][q][r]<<"\n";
if(j != 0 && r == 1)dp[i][j][q][r] = min(min(dp[i-1][j-1][q][(r+1)%3],dp[i-1][j-1][q][(r+2)%3])+max(0,sa[fb[j-1]]-(i-j-q))+max(0,sc[fb[j-1]]-q),dp[i][j][q][r]);
//if(i == 4&&j == 1&&q == 1&& r == 1) cout<<dp[i][j][q][r]<<"\n";
if(q!= 0 && r == 2)dp[i][j][q][r] = min(min(dp[i-1][j][q-1][(r+1)%3],dp[i-1][j][q-1][(r+2)%3])+max(0,sa[fc[q-1]]-(i-j-q))+max(0,sb[fc[q-1]]-j),dp[i][j][q][r]);
//cout<<i<<" "<<j<<" "<<q<<" "<<r<<" "<<dp[i][j][q][r]<<"\n";
dp[i][j][q][r] = min(dp[i][j][q][r],1000000000);
}
}
}
}
long long ans = 1e9;
for(int i = 0;i<3;i++)
{
ans = min(dp[n][sb[n]][sc[n]][i],ans);
}
if(ans >= 1e9)
{
cout<<-1;
return 0;
}
cout<<ans;
}