Submission #1190212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190212		DangKhoizzzz	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	65 ms	162888 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e9;
const int maxn = 4e2 + 2;

char s[maxn];
int n , dp[maxn][maxn][maxn][3] , cntr[maxn] , cntg[maxn] , cntb[maxn];
vector <int> posr = {-1} , posg = {-1} , posb = {-1};

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i];
    for(int i = 1; i <= n; i++)
    {
        cntr[i] = cntr[i-1];
        cntg[i] = cntg[i-1];
        cntb[i] = cntb[i-1];

        if(s[i] == 'R') 
        {
            posr.push_back(i);
            cntr[i]++;
        }
        else if(s[i] == 'G') 
        {
            posg.push_back(i);
            cntg[i]++;
        }
        else // B
        {
            posb.push_back(i);
            cntb[i]++;
        }

        if(max({cntr[i] , cntg[i] , cntb[i]}) > (n+1)/2)
        {
            cout << -1 << '\n';
            return;
        } 
    }

    for(int r = 0; r < posr.size(); r++)
    {
        for(int g = 0; g < posg.size(); g++)
        {
            for(int b = 0; b < posb.size(); b++)
            {
                if(r == 0 && g == 0 && b == 0) continue;

                // case R - 0 case
                if(r > 0)
                {
                    dp[r][g][b][0] = min(dp[r-1][g][b][1] , dp[r-1][g][b][2]) + max(0 , g - cntg[posr[r]]) + max(0 , b - cntb[posr[r]]);
                }
                else dp[r][g][b][0] = INF;
                // case G - 1 case
                if(g > 0)
                {
                    dp[r][g][b][1] = min(dp[r][g-1][b][0] , dp[r][g-1][b][2]) + max(0 , r - cntr[posg[g]]) + max(0 , b - cntb[posg[g]]);
                }
                else dp[r][g][b][1] = INF;
                // case B - 2 case
                if(b > 0)
                {
                    dp[r][g][b][2] = min(dp[r][g][b-1][0] , dp[r][g][b-1][1]) + max(0 , r - cntr[posb[b]]) + max(0 , g - cntg[posb[b]]);
                }
                else dp[r][g][b][2] = INF;
            }
        }
    }

    int ans = INF;
    for(int i = 0; i < 3; i++)
    {
        ans = min(dp[posr.size() - 1][posg.size() - 1][posb.size() - 1][i] , ans);
    }
    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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