Submission #559940

#	Time	Username	Problem	Language	Result	Execution time	Memory
559940		Tien_Noob	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	59 ms	95676 KiB

joi2019_ho_t3

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 200;
vector<int> pos[3];
int cnt[3], dp[N + 1][N + 1][N + 1][3], f[2 * N + 1][3];
int n;
string s;
int convert(char c)
{
    if (c == 'R')
    {
        return 0;
    }
    if (c == 'G')
    {
        return 1;
    }
    if (c == 'Y')
    {
        return 2;
    }
}
void read()
{
    pos[0] = pos[1] = pos[2] = {0};
    cin >> n >> s;
    int i = 0;
    for (char &c : s)
    {
        ++i;
        ++cnt[convert(c)];
        for (int j = 0; j < 3; ++ j)
        {
            f[i][j] = f[i - 1][j];
        }
        ++f[i][convert(c)];
        pos[convert(c)].push_back(i);
    }
}
bool minimize(int &a, int b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
int dis(int i, int j, int k, int t)
{
    if (t == 0)
    {
        return pos[0][i] - i - f[min(pos[0][i], pos[1][j])][1] - f[min(pos[0][i], pos[2][k])][2];
    }
    if (t == 1)
    {
        return pos[1][j] - j  - f[min(pos[1][j], pos[0][i])][0] - f[min(pos[1][j], pos[2][k])][2];
    }
    if (t == 2)
    {
        return pos[2][k] - k  - f[min(pos[2][k], pos[0][i])][0] - f[min(pos[2][k], pos[1][j])][1];
    }
}
void solve()
{
    if (max({cnt[0], cnt[1], cnt[2]}) > (n + 1)/2)
    {
        cout << -1;
        return ;
    }
    for (int i = 0; i <= cnt[0]; ++ i)
    {
        for (int j = 0; j <= cnt[1]; ++ j)
        {
            for (int k = 0; k <= cnt[2]; ++ k)
            {
                for (int l = 0; l < 3; ++ l)
                {
                    if (i == 0 && j == 0 && k == 0)
                    {
                        dp[i][j][k][l] = 0;
                    }
                    else
                    {
                        dp[i][j][k][l] = 1e9;
                    }
                }
                if (i > 0)
                {
                    minimize(dp[i][j][k][0], min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + dis(i, j, k, 0));
                }
                if (j > 0)
                {
                    minimize(dp[i][j][k][1], min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + dis(i, j, k, 1));
                }
                if (k > 0)
                {
                    minimize(dp[i][j][k][2], min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + dis(i, j, k, 2));
                }
                //cerr << i << ' ' << j  << ' ' << k << ' ' << dp[i][j][k][0] << ' ' << dp[i][j][k][1] << ' ' << dp[i][j][k][2] << '\n';
            }
        }
    }
    int res = 1e9;
    for (int i = 0; i < 3; ++ i)
    {
        res = min(res, dp[cnt[0]][cnt[1]][cnt[2]][i]);
    }
    cout << res;
}
int  main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int convert(char)':
joi2019_ho_t3.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^
joi2019_ho_t3.cpp: In function 'int dis(int, int, int, int)':
joi2019_ho_t3.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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