Submission #934534

#	Time	Username	Problem	Language	Result	Execution time	Memory
934534		Hanksburger	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	34 ms	31400 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, pos[405][3], cnt[405][3];
    string str;
    cin >> n >> str;
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<3; j++)
            cnt[i][j]=i?cnt[i-1][j]:0;
        if (str[i]=='R')
            pos[++cnt[i][0]][0]=i;
        else if (str[i]=='G')
            pos[++cnt[i][1]][1]=i;
        else
            pos[++cnt[i][2]][2]=i;
    }
    int dp[cnt[n-1][0]+5][cnt[n-1][1]+5][cnt[n-1][2]+5][3], ans=1e9;
    for (int i=0; i<=cnt[n-1][0]; i++)
    {
        for (int j=0; j<=cnt[n-1][1]; j++)
        {
            for (int k=0; k<=cnt[n-1][2]; k++)
            {
                if (i==0 && j==0 && k==0)
                {
                    for (int l=0; l<3; l++)
                        dp[i][j][k][l]=0;
                    continue;
                }
                dp[i][j][k][0]=i?min(dp[i-1][j][k][1], dp[i-1][j][k][2])+max(0, cnt[pos[i][0]][0]-i)+max(0, cnt[pos[i][0]][1]-j)+max(0, cnt[pos[i][0]][2]-k):1e9;
                dp[i][j][k][1]=j?min(dp[i][j-1][k][0], dp[i][j-1][k][2])+max(0, cnt[pos[j][1]][0]-i)+max(0, cnt[pos[j][1]][1]-j)+max(0, cnt[pos[j][1]][2]-k):1e9;
                dp[i][j][k][2]=k?min(dp[i][j][k-1][0], dp[i][j][k-1][1])+max(0, cnt[pos[k][2]][0]-i)+max(0, cnt[pos[k][2]][1]-j)+max(0, cnt[pos[k][2]][2]-k):1e9;
            }
        }
    }
    for (int i=0; i<3; i++)
        ans=min(ans, dp[cnt[n-1][0]][cnt[n-1][1]][cnt[n-1][2]][i]);
    cout << (ans>=1e8?-1:ans);
}

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