Submission #1159238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159238		vicvic	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	15 / 100	61 ms	163100 KiB

joi2019_ho_t3

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
string s;
int n;
vector <int> poz[3];
int before[405][3];
int dp[405][405][405][3];
int main ()
{
    cin >> n;
    cin >> s;
    for (int i=0;i<n;i++)
    {
        if (s[i]=='R') poz[0].push_back (i+1);
        if (s[i]=='G') poz[1].push_back (i+1);
        if (s[i]=='Y') poz[2].push_back (i+1);
        before[i+1][0]=poz[0].size();
        before[i+1][1]=poz[1].size();
        before[i+1][2]=poz[2].size();
    }
    for (int i=0;i<=poz[0].size();i++)
    {
        for (int j=0;j<=poz[1].size();j++)
        {
            for (int k=0;k<=poz[2].size();k++)
            {
                if (!i && !j && !k)
                    continue;
                for (int l=0;l<=2;l++)
                {
                    dp[i][j][k][l]=1e9;
                }
                int total=i+j+k;
                if (i) dp[i][j][k][0]=min (dp[i-1][j][k][1], dp[i-1][j][k][2])+(poz[0][i-1]+max (j-before[poz[0][i-1]][1], 0)+max (k-before[poz[0][i-1]][2], 0))-total;
                if (j) dp[i][j][k][1]=min (dp[i][j-1][k][0], dp[i][j-1][k][2])+(poz[1][j-1]+max (i-before[poz[1][j-1]][0], 0)+max (k-before[poz[1][j-1]][2], 0))-total;
                if (k) dp[i][j][k][2]=min (dp[i][j][k-1][0], dp[i][j][k-1][1])+(poz[2][k-1]+max (i-before[poz[2][k-1]][0], 0)+max (j-before[poz[2][k-1]][1], 0))-total;
            }
        }
    }
    int mn=min (dp[poz[0].size()][poz[1].size()][poz[2].size()][0], min (dp[poz[0].size()][poz[1].size()][poz[2].size()][1], dp[poz[0].size()][poz[1].size()][poz[2].size()][2]));
    cout << (mn==1e9?-1:mn);
    return 0;
}

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