Submission #754636

#	Time	Username	Problem	Language	Result	Execution time	Memory
754636		Kihihihi	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	399 ms	780492 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];

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 };
                if (idx[0] > 0)
                {
                    int aft = max(idx[1] - cnt[1][pos[0][idx[0] - 1]], 0) + max(idx[2] - cnt[2][pos[0][idx[0] - 1]], 0);
                    int npos = pos[0][idx[0] - 1] + aft;
                    int dist = abs(npos - (i + j + k - 1));
                    dp[i][j][k][0] = min(dp[i][j][k][0], min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + dist);
                }
                if (idx[1] > 0)
                {
                    int aft = max(idx[0] - cnt[0][pos[1][idx[1] - 1]], 0) + max(idx[2] - cnt[2][pos[1][idx[1] - 1]], 0);
                    int npos = pos[1][idx[1] - 1] + aft;
                    int dist = abs(npos - (i + j + k - 1));
                    dp[i][j][k][1] = min(dp[i][j][k][1], min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + dist);
                }
                if (idx[2] > 0)
                {
                    int aft = max(idx[0] - cnt[0][pos[2][idx[2] - 1]], 0) + max(idx[1] - cnt[1][pos[2][idx[2] - 1]], 0);
                    int npos = pos[2][idx[2] - 1] + aft;
                    int dist = abs(npos - (i + j + k - 1));
                    dp[i][j][k][2] = min(dp[i][j][k][2], min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + 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: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[0].size() + 1; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int j = 0; j < pos[1].size() + 1; j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int k = 0; k < pos[2].size() + 1; k++)
      |                             ~~^~~~~~~~~~~~~~~~~~~

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