Submission #590007

#	Time	Username	Problem	Language	Result	Execution time	Memory
590007		boris_mihov	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	451 ms	130112 KiB

joi2019_ho_t3

#include <algorithm>
#include <iostream>
#include <vector>

typedef long long llong;
const int MAXN = 400 + 10;
const int INF = 1e9;

int n;
char s[MAXN];
int dp[MAXN][MAXN][MAXN][4];
bool bl[MAXN][MAXN][MAXN][4];
int byPos[4][MAXN];
int len[4];

int binary(int a[], int bound, int border)
{
    int l = -1, r = bound, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (a[mid] <= border) l = mid;
        else r = mid;
    }

    return bound - 1 - l;
}

int f(int ones, int twos, int threes, int last)
{
    if (ones + twos + threes == n) return 0;
    if (bl[ones][twos][threes][last]) return dp[ones][twos][threes][last];
    
    bl[ones][twos][threes][last] = true;
    dp[ones][twos][threes][last] = INF;

    if (last != 1 && ones != len[1])
    {
        int add = binary(byPos[2], twos, byPos[1][ones]) + binary(byPos[3], threes, byPos[1][ones]);
        dp[ones][twos][threes][last] = std::min(dp[ones][twos][threes][last], f(ones + 1, twos, threes, 1) + add + byPos[1][ones] - (ones + twos + threes + 1));
    }

    if (last != 2 && twos != len[2])
    {
        int add = binary(byPos[1], ones, byPos[2][twos]) + binary(byPos[3], threes, byPos[2][twos]);
        dp[ones][twos][threes][last] = std::min(dp[ones][twos][threes][last], f(ones, twos + 1, threes, 2) + add + byPos[2][twos] - (ones + twos + threes + 1));
    }

    if (last != 3 && threes != len[3])
    {
        int add = binary(byPos[1], ones, byPos[3][threes]) + binary(byPos[2], twos, byPos[3][threes]);
        dp[ones][twos][threes][last] = std::min(dp[ones][twos][threes][last], f(ones, twos, threes + 1, 3) + add + byPos[3][threes] - (ones + twos + threes + 1));
    }

    return dp[ones][twos][threes][last];
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        if (s[i] == 'R') s[i] = '1';
        if (s[i] == 'G') s[i] = '2';
        if (s[i] == 'Y') s[i] = '3';
        byPos[s[i]-'0'][len[s[i]-'0']++] = i;
    }

    int result = f(0, 0, 0, 0);
    if (result == INF) result = -1;
    std::cout << result << '\n';
}

void read()
{
    std::cin >> n;
    std::cin >> s + 1;
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main ()
{
    fastIO();
    read();
    solve();

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void read()':
joi2019_ho_t3.cpp:76:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     std::cin >> s + 1;
      |                 ~~^~~

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