Submission #754628

#	Time	Username	Problem	Language	Result	Execution time	Memory
754628		Kihihihi	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	516 ms	780508 KiB

joi2019_ho_t3

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e9, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);

const int N = 405;

int dp[N][N][N][3];

int after(vector<int> idx, vector<vector<int>>& pos, vector<vector<int>>& cnt, int nd)
{
    int res = 0;
    for (int i = 0; i < 3; i++)
    {
        if (i == nd)
        {
            continue;
        }

        if (idx[i] > 0 && pos[nd][idx[nd] - 1] < pos[i][idx[i] - 1])
        {
            res += cnt[i][pos[i][idx[i] - 1]] - cnt[i][pos[nd][idx[nd] - 1]];
        }
    }
    return res;
}

void solve()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                for (int lst = 0; lst < 3; lst++)
                {
                    dp[i][j][k][lst] = INF;
                }
            }
        }
    }
    for (int lst = 0; lst < 3; lst++)
    {
        dp[0][0][0][lst] = 0;
    }

    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> pos(3), cnt(3, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'R')
        {
            pos[0].push_back(i);
        }
        else if (s[i] == 'G')
        {
            pos[1].push_back(i);
        }
        else
        {
            pos[2].push_back(i);
        }

        for (int j = 0; j < 3; j++)
        {
            cnt[j][i] = pos[j].size();
        }
    }

    for (int i = 0; i < pos[0].size() + 1; i++)
    {
        for (int j = 0; j < pos[1].size() + 1; j++)
        {
            for (int k = 0; k < pos[2].size() + 1; k++)
            {
                if (max({ i, j, k }) >= (i + j + k + 1) / 2 + 1)
                {
                    continue;
                }

                vector<int> idx = { i, j, k };
                for (int lst = 0; lst < 3; lst++)
                {
                    if (idx[lst] == 0)
                    {
                        continue;
                    }

                    int aft = after(idx, pos, cnt, lst);
                    for (int pr = 0; pr < 3; pr++)
                    {
                        if (lst == pr)
                        {
                            continue;
                        }

                        int ii = i, jj = j, kk = k;
                        if (lst == 0)
                        {
                            ii--;
                        }
                        else if (lst == 1)
                        {
                            jj--;
                        }
                        else
                        {
                            kk--;
                        }

                        if (dp[ii][jj][kk][pr] != INF)
                        {
                            int npos = pos[lst][idx[lst] - 1] + aft;
                            int dist = abs(npos - (i + j + k - 1));
                            dp[i][j][k][lst] = min(dp[i][j][k][lst], dp[ii][jj][kk][pr] + dist);
                        }
                    }
                }
            }
        }
    }

    int ans = INF;
    for (int lst = 0; lst < 3; lst++)
    {
        ans = min(ans, dp[pos[0].size()][pos[1].size()][pos[2].size()][lst]);
    }
    cout << (ans == INF ? -1 : ans) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    int tst = 1;
    //cin >> tst;
    while (tst--)
    {
        solve();
    }

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

Compilation message (stderr)

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

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