Submission #777253

#	Time	Username	Problem	Language	Result	Execution time	Memory
777253		DobromirAngelov	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	85 ms	162980 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAXN=405;
const int INF=1e9+5;

int n;
string s;
int a[MAXN];
vector<int> pos[3];
int prevs[MAXN][3];
int dp[MAXN][MAXN][MAXN][3];

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n;
cin>>s;
for(int i=0;i<n;i++)
{
    a[i]=(s[i]=='R' ? 0 : (s[i]=='G' ? 1 : 2));
}

for(int i=0;i<n;i++)
    pos[a[i]].push_back(i);

for(int i=0;i<=n;i++)
{
    for(int j=0;j<3;j++)
        if(i>0) prevs[i][j]+=prevs[i-1][j];
    prevs[i+1][a[i]]++;
}

for(int i=0;i<=prevs[n][0];i++)
    for(int j=0;j<=prevs[n][1];j++)
        for(int k=0;k<=prevs[n][2];k++)
            for(int t=0;t<3;t++) dp[i][j][k][t]=INF;

dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
for(int i=0;i<=prevs[n][0];i++)
{
    for(int j=0;j<=prevs[n][1];j++)
    {
        for(int k=0;k<=prevs[n][2];k++)
        {
            if(i>0) dp[i][j][k][0]=min(dp[i][j][k][0], dp[i-1][j][k][1] + max(0, prevs[pos[0][i-1]][1]-j) + max(0, prevs[pos[0][i-1]][2]-k));
            if(i>0) dp[i][j][k][0]=min(dp[i][j][k][0], dp[i-1][j][k][2] + max(0, prevs[pos[0][i-1]][1]-j) + max(0, prevs[pos[0][i-1]][2]-k));

            if(j>0) dp[i][j][k][1]=min(dp[i][j][k][1], dp[i][j-1][k][0] + max(0, prevs[pos[1][j-1]][0]-i) + max(0, prevs[pos[1][j-1]][2]-k));
            if(j>0) dp[i][j][k][1]=min(dp[i][j][k][1], dp[i][j-1][k][2] + max(0, prevs[pos[1][j-1]][0]-i) + max(0, prevs[pos[1][j-1]][2]-k));

            if(k>0) dp[i][j][k][2]=min(dp[i][j][k][2], dp[i][j][k-1][0] + max(0, prevs[pos[2][k-1]][0]-i) + max(0, prevs[pos[2][k-1]][1]-j));
            if(k>0) dp[i][j][k][2]=min(dp[i][j][k][2], dp[i][j][k-1][1] + max(0, prevs[pos[2][k-1]][0]-i) + max(0, prevs[pos[2][k-1]][1]-j));
        }
    }
}

int ans=min(dp[prevs[n][0]][prevs[n][1]][prevs[n][2]][0],
            min(dp[prevs[n][0]][prevs[n][1]][prevs[n][2]][1],
                dp[prevs[n][0]][prevs[n][1]][prevs[n][2]][2]));
if(ans==INF) cout<<-1<<endl;
else cout<<ans<<endl;

return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25