Submission #1178839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178839		MongHwa	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	110 ms	159048 KiB

joi2019_ho_t3

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <vector>
using namespace std;

#define INF 0x7f7f7f7f

int r, g, y;
vector<int> rv, gv, yv;
int dp[201][201][201][3];
int val1[201][201][201];
int val2[201][201][201];
int val3[201][201][201];

int go(int rcnt, int gcnt, int ycnt, int pre)
{
    if(rcnt == r && gcnt == g && ycnt == y)
        return 0;
    
    int& ret = dp[rcnt][gcnt][ycnt][pre];
    if(ret != -1)
        return ret;
    
    ret = INF;
    if(pre == 0)
    {
        if(gcnt < g)
            ret = min(ret, go(rcnt, gcnt+1, ycnt, 1) + abs(rcnt+gcnt+ycnt-(gv[gcnt]+val2[gcnt][rcnt][ycnt])));
        if(ycnt < y)
            ret = min(ret, go(rcnt, gcnt, ycnt+1, 2) + abs(rcnt+gcnt+ycnt-(yv[ycnt]+val3[ycnt][rcnt][gcnt])));
    }
    else if(pre == 1)
    {
        if(rcnt < r)
            ret = min(ret, go(rcnt+1, gcnt, ycnt, 0) + abs(rcnt+gcnt+ycnt-(rv[rcnt]+val1[rcnt][gcnt][ycnt])));
        if(ycnt < y)
            ret = min(ret, go(rcnt, gcnt, ycnt+1, 2) + abs(rcnt+gcnt+ycnt-(yv[ycnt]+val3[ycnt][rcnt][gcnt])));
    }
    else
    {
        if(rcnt < r)
            ret = min(ret, go(rcnt+1, gcnt, ycnt, 0) + abs(rcnt+gcnt+ycnt-(rv[rcnt]+val1[rcnt][gcnt][ycnt])));
        if(gcnt < g)
            ret = min(ret, go(rcnt, gcnt+1, ycnt, 1) + abs(rcnt+gcnt+ycnt-(gv[gcnt]+val2[gcnt][rcnt][ycnt])));
    }

    return ret;
}

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')
        {
            r++;
            rv.push_back(i);
        }
        else if(s[i] == 'G')
        {
            g++;
            gv.push_back(i);
        }
        else
        {
            y++;
            yv.push_back(i);
        }
    }

    if(r-1 > g+y || g-1 > r+y || y-1 > r+g)
    {
        cout << "-1\n";
        return 0;
    }

    for(int i = 0; i <= r; i++)
        for(int j = 0; j <= g; j++)
            for(int k = 0; k <= y; k++)
                dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = -1;

    for(int i = 0; i < r; i++)
    {
        int cnt1 = 0;
        for(int j = 0; j <= g; j++)
        {
            int cnt2 = 0;
            for(int k = 0; k <= y; k++)
            {
                val1[i][j][k] = cnt1+cnt2;
                if(k < y && rv[i] < yv[k])
                    cnt2++;
            }

            if(j < g && rv[i] < gv[j])
                cnt1++;
        }
    }

    for(int i = 0; i < g; i++)
    {
        int cnt1 = 0;
        for(int j = 0; j <= r; j++)
        {
            int cnt2 = 0;
            for(int k = 0; k <= y; k++)
            {
                val2[i][j][k] = cnt1+cnt2;
                if(k < y && gv[i] < yv[k])
                    cnt2++;
            }

            if(j < r && gv[i] < rv[j])
                cnt1++;
        }
    }

    for(int i = 0; i < y; i++)
    {
        int cnt1 = 0;
        for(int j = 0; j <= r; j++)
        {
            int cnt2 = 0;
            for(int k = 0; k <= g; k++)
            {
                val3[i][j][k] = cnt1+cnt2;
                if(k < g && yv[i] < gv[k])
                    cnt2++;
            }

            if(j < r && yv[i] < rv[j])
                cnt1++;
        }
    }
    
    int ans = min(go(0, 0, 0, 0), min(go(0, 0, 0, 1), go(0, 0, 0, 2)));
    if(ans == INF)
        cout << "-1\n";
    else
        cout << ans << '\n';
}

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