Submission #1180821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180821		miniob	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	75 ms	163856 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

int dp[407][407][407][4];
int pom[3][407][407];
vector<int> pos[3];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        if(s[i] == 'R')
        {
        	pos[0].push_back(i);
        }
        else if(s[i] == 'G')
        {
        	pos[1].push_back(i);
        }
        else if(s[i] == 'Y')
        {
        	pos[2].push_back(i);
        }
    }
    
    for (int i = 0; i < 3; i++)
    {
        if (pos[i].size() > (n + 1) / 2)
        {
            cout << -1 << endl;
            return 0;
        }
    }

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j <= pos[i].size(); j++)
        {
            for (int k = 0; k <= n; k++)
            {
                if(j == 0) 
                {
                    pom[i][j][k] = 0;
                } 
                else 
                {
                    pom[i][j][k] = pom[i][j - 1][k];
                    if(k > pos[i][j - 1])
                    {
                    	pom[i][j][k]++;
                    }
                }
            }
        }
    }
    

    for (int i = 0; i <= pos[0].size(); i++)
    {
        for (int j = 0; j <= pos[1].size(); j++)
        {
            for (int k = 0; k <= pos[2].size(); k++)
            {
                for (int l = 0; l < 4; l++)
                {
                    dp[i][j][k][l] = 8000000;
                }
            }
        }
    }
    dp[0][0][0][3] = 0;
    for(int i = 0; i <= pos[0].size(); i++)
    {
        for(int j = 0; j <= pos[1].size(); j++)
        {
            for(int k = 0; k <= pos[2].size(); k++)
            {
                for(int pop = 0; pop < 4; pop++)
                {
                    if(dp[i][j][k][pop] == 8000000)
                    {
                    	continue;
                    }
                    for (int c = 0; c < 3; c++)
                    {
                        if(pop != 3 && c == pop)
                        {
                        	 continue;
                        }
                        if(c == 0 && i < pos[0].size())
                        {
                            dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][pop] + pos[0][i] - (pom[0][i][pos[0][i]] + pom[1][j][pos[0][i]] + pom[2][k][pos[0][i]]));
                        }
                        if(c == 1 && j < pos[1].size())
                        {
                            dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][pop] + pos[1][j] - (pom[0][i][pos[1][j]] + pom[1][j][pos[1][j]] + pom[2][k][pos[1][j]]));
                        }
                        if(c == 2 && k < pos[2].size())
                        {
                            dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], dp[i][j][k][pop] + pos[2][k] - (pom[0][i][pos[2][k]] + pom[1][j][pos[2][k]] + pom[2][k][pos[2][k]]));
                        }
                    }
                }
            }
        }
    }
    int odp = 8000000;
    for (int i = 0; i < 3; i++)
    {
        odp = min(odp, dp[pos[0].size()][pos[1].size()][pos[2].size()][i]);
    }
    if(odp == 8000000)
    {
    	cout << -1 << endl;
    }
    else
    {
    	cout << odp << endl;
    }
    return 0;
}

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