Submission #642332

#	Time	Username	Problem	Language	Result	Execution time	Memory
642332		danikoynov	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	0 ms	340 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];
pair < int, int > prf[3][maxn];
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 i = 0; i < pos[0].size(); i ++)
    {
        int f1 = 0;
        while(f1 < pos[1].size() && pos[0][i] > pos[1][f1])
            f1 ++;

        int f2 = 0;
        while(f2 < pos[2].size() && pos[0][i] > pos[2][f2])
            f2 ++;
            ///cout << i << " " << f1 << " " << f2 << endl;

        prf[0][i] = {f1, f2};
    }

    for (int i = 0; i < pos[1].size(); i ++)
    {
        int f1 = 0;
        while(f1 < pos[0].size() && pos[1][i] > pos[0][f1])
            f1 ++;

        int f2 = 0;
        while(f2 < pos[2].size() && pos[1][i] > pos[2][f2])
            f2 ++;

        prf[1][i] = {f1, f2};
    }


    for (int i = 0; i < pos[2].size(); i ++)
    {
        int f1 = 0;
        while(f1 < pos[0].size() && pos[2][i] > pos[0][f1])
            f1 ++;

        int f2 = 0;
        while(f2 < pos[1].size() && pos[2][i] > pos[1][f2])
            f2 ++;

        prf[2][i] = {f1, f2};
    }
    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))
                        + max(0, j - prf[0][i].first)
                        + max(0, k - prf[0][i].second);
                    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))
                        + max(0, i - prf[1][i].first)
                        + max(0, k - prf[1][i].second);
                    /**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)
                        + max(0, i - prf[2][i].first)
                        + max(0, j - prf[2][i].second);
                    /**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:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i <= pos[0].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int j = 0; j <= pos[1].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:46:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for (int k = 0; k <= pos[2].size(); k ++)
      |                             ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i < pos[0].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         while(f1 < pos[1].size() && pos[0][i] > pos[1][f1])
      |               ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         while(f2 < pos[2].size() && pos[0][i] > pos[2][f2])
      |               ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < pos[1].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(f1 < pos[0].size() && pos[1][i] > pos[0][f1])
      |               ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         while(f2 < pos[2].size() && pos[1][i] > pos[2][f2])
      |               ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < pos[2].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         while(f1 < pos[0].size() && pos[2][i] > pos[0][f1])
      |               ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         while(f2 < pos[1].size() && pos[2][i] > pos[1][f2])
      |               ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |                 if (k > pos[2].size())
      |                     ~~^~~~~~~~~~~~~~~

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