Submission #589994

#	Time	Username	Problem	Language	Result	Execution time	Memory
589994		boris_mihov	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	1022 ms	108716 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];
std::vector < int > byPos[4];

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 != byPos[1].size())
    {
        int add = 0;
        for (int i = 0 ; i < twos ; ++i)
        {
            if (byPos[2][i] > byPos[1][ones]) add++; 
        }

        for (int i = 0 ; i < threes ; ++i)
        {
            if (byPos[3][i] > byPos[1][ones]) add++; 
        }

        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 != byPos[2].size())
    {
        int add = 0;
        for (int i = 0 ; i < ones ; ++i)
        {
            if (byPos[1][i] > byPos[2][twos]) add++; 
        }

        for (int i = 0 ; i < threes ; ++i)
        {
            if (byPos[3][i] > byPos[2][twos]) add++; 
        }

        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 != byPos[3].size())
    {
        int add = 0;
        for (int i = 0 ; i < ones ; ++i)
        {
            if (byPos[1][i] > byPos[3][threes]) add++; 
        }

        for (int i = 0 ; i < twos ; ++i)
        {
            if (byPos[2][i] > byPos[3][threes]) add++; 
        }

        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'].push_back(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 'int f(int, int, int, int)':
joi2019_ho_t3.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if (last != 1 && ones != byPos[1].size())
      |                      ~~~~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     if (last != 2 && twos != byPos[2].size())
      |                      ~~~~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:55:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     if (last != 3 && threes != byPos[3].size())
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void read()':
joi2019_ho_t3.cpp:92:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     std::cin >> s + 1;
      |                 ~~^~~

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