Submission #1231310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231310		badge881	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	67 ms	163284 KiB

joi2019_ho_t3

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

const int MX = 450, INF = 1'000'000'000;

int dp[MX][MX][MX][3];
int cumulRed[MX], cumulGreen[MX], cumulYellow[MX];
vector<int> whereRed, whereGreen, whereYellow;
int nbRed = 0, nbGreen = 0, nbYellow = 0;

int main()
{
    int n;
    char s[MX];
    scanf("%d\n%s\n", &n, s);
    cumulRed[0] = cumulGreen[0] = cumulYellow[0] = 0; // init

    for (int i = 1; i <= n; i++)
    {
        cumulRed[i] = cumulRed[i - 1];
        cumulGreen[i] = cumulGreen[i - 1];
        cumulYellow[i] = cumulYellow[i - 1];
        switch (s[i - 1]) // cause for 1 to n, not 0 to n-1
        {
        case 'R':
            whereRed.push_back(i);
            cumulRed[i]++;
            nbRed++;
            break;

        case 'G':
            whereGreen.push_back(i);
            cumulGreen[i]++;
            nbGreen++;
            break;

        case 'Y':
            whereYellow.push_back(i);
            cumulYellow[i]++;
            nbYellow++;
            break;

        default:
            break;
        }
    }

    auto rg = [&](int i)
    {
        return min(INF, max(0, i));
    };

    // situation:
    // they stills r red, g green and y yellow
    // 0: i want red
    // 1: i want green
    // 2: i want yellow
    // rg is a function that make the result always in the range [0, INF]

    for (int r = 0; r <= nbRed; r++)
    {
        for (int g = 0; g <= nbGreen; g++)
        {
            for (int y = 0; y <= nbYellow; y++)
            {
                dp[r][g][y][0] = dp[r][g][y][1] = dp[r][g][y][2] = INF;

                if (r + g + y == 0) // the end or the beginnig ?
                {
                    dp[r][g][y][0] = dp[r][g][y][1] = dp[r][g][y][2] = 0;
                    continue;
                }

                if (r != 0) // there still some red so i want a red here
                    dp[r][g][y][0] = rg(
                        min(dp[r - 1][g][y][1], dp[r - 1][g][y][2]) // i want some green or yellow
                        + rg(cumulGreen[whereRed[r - 1]] - g)       // move a green here
                        + rg(cumulYellow[whereRed[r - 1]] - y)      // move a yellow here
                    );

                if (g != 0) // there still some green so i want a green here
                    dp[r][g][y][1] = rg(
                        min(dp[r][g - 1][y][0], dp[r][g - 1][y][2]) // i want some red or yellow
                        + rg(cumulRed[whereGreen[g - 1]] - r)       // move a red here
                        + rg(cumulYellow[whereGreen[g - 1]] - y)    // move a yellow here
                    );

                if (y != 0) // there still some yellow so i want a yellow here
                    dp[r][g][y][2] = rg(
                        min(dp[r][g][y - 1][0], dp[r][g][y - 1][1]) // i want some red or green
                        + rg(cumulRed[whereYellow[y - 1]] - r)      // move a red here
                        + rg(cumulGreen[whereYellow[y - 1]] - g)    // move a green here
                    );
            }
        }
    }

    int ans = min({dp[nbRed][nbGreen][nbYellow][0],
                   dp[nbRed][nbGreen][nbYellow][1],
                   dp[nbRed][nbGreen][nbYellow][2]});
    if (ans == INF)
        ans = -1;

    printf("%d\n", ans);

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d\n%s\n", &n, s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

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