Submission #642322

#	Time	Username	Problem	Language	Result	Execution time	Memory
642322		danikoynov	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	833 ms	163020 KiB

joi2019_ho_t3

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 410, inf = 1e9;

int n, a[maxn], dp[maxn][maxn][maxn][3];
string s;
vector < int > pos[3];
void solve()
{
    cin >> n >> s;
    for (int i = 0; i < n; i ++)
    {
        if (s[i] == 'R')
            a[i + 1] = 0;
        else if (s[i] == 'G')
            a[i + 1] = 1;
        else if (s[i] == 'Y')
            a[i + 1] = 2;
    }

    for (int i = 1; i <= n; i ++)
        pos[a[i]].push_back(i);

    for (int i = 0; i <= pos[0].size(); i ++)
        for (int j = 0; j <= pos[1].size(); j ++)
            for (int k = 0; k <= pos[2].size(); k ++)
                dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = inf;

    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;

    for (int p = 0; p < n; p ++)
    {
        for (int i = 0; i <= min(p, (int)pos[0].size()); i ++)
            for (int j = 0; j <= min(p - i, (int)(pos[1].size())); j ++)
            {
                int k = p - i - j;
                if (k > pos[2].size())
                    continue;

                ///cout << i << " " << j << " " << k << " " << dp[i][j][k][0] << " " << dp[i][j][k][1] << " " << dp[i][j][k][2] << endl;
                if (i < (int)pos[0].size())
                {
                    int add0 = min(dp[i][j][k][1], dp[i][j][k][2]);
                    int sd = (pos[0][i] - (p + 1));
                    for (int f = 0; f < j; f ++)
                        if (pos[1][f] > pos[0][i])
                        sd ++;
                    for (int f = 0; f < k; f ++)
                        if (pos[2][f] > pos[0][i])
                        sd ++;
                    add0 = add0 + max(0, sd);
                    dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], add0);
                }

                if (j < (int)pos[1].size())
                {
                    ///cout << "here" << endl;
                    int add1 = min(dp[i][j][k][0], dp[i][j][k][2]);
                    int sd = (pos[1][j] - (p + 1));
                    for (int f = 0; f < i; f ++)
                        if (pos[0][f] > pos[1][j])
                        sd ++;
                    for (int f = 0; f < k; f ++)
                        if (pos[2][f] > pos[1][j])
                        sd ++;
                    add1 = add1 + max(0, sd);
                    dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], add1);
                }

                if (k < (int)pos[2].size())
                {
                    int add2 = min(dp[i][j][k][0], dp[i][j][k][1]);
                    int sd = pos[2][k] - (p + 1);
                    for (int f = 0; f < i; f ++)
                        if (pos[0][f] > pos[2][k])
                        sd ++;
                    for (int f = 0; f < j; f ++)
                        if (pos[1][f] > pos[2][k])
                        sd ++;
                    add2 = add2 + max(0, sd);
                    dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], add2);
                }
            }
    }
    ///cout << dp[1][1][0][1] << endl;


    int ans = inf;
    for (int last = 0; last < 3; last ++)
        ans = min(ans, dp[pos[0].size()][pos[1].size()][pos[2].size()][last]);

    if (ans >= inf)
        cout << -1 << endl;
    else
        cout << ans << endl;

}

int main()
{
    solve();
    return 0;
}

/**
15
YYYRRRRRGGGGGGG
*/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i <= pos[0].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int j = 0; j <= pos[1].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for (int k = 0; k <= pos[2].size(); k ++)
      |                             ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                 if (k > pos[2].size())
      |                     ~~^~~~~~~~~~~~~~~

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