Submission #871337

#	Time	Username	Problem	Language	Result	Execution time	Memory
871337		hct_2so1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	187 ms	757700 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define sz(v) ((ll) (v).size())
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define F first
#define S second
#define pii(x, y) make_pair(x, y)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define lg(x) (63 - __builtin_clz(x))

template <class X, class Y>
    bool minimize(X &x, const Y &y)
    {
        if (x > y) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y)
    {
        if (x < y) {x = y; return 1;}
        return 0;
    }

using namespace std;
typedef long long ll;
const int N = 400 + 5;
const int M = 6e5;
const int mod = 998244353;
const int INF = 1e9 + 7;
const ll oo = 2e18;
const double eps = 1e-1;
const long double pi = 2*acos(0.0);

int n, cnt[N][3], mp[100];
vector<int> v[3];
string s;

void Input(void)
{
    mp['R'] = 0, mp['G'] = 1, mp['Y'] = 2;
    cin >> n >> s;
    s = ' ' + s;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 0; j < 3; j ++) cnt[i][j] = cnt[i - 1][j];
        cnt[i][mp[s[i]]] ++;
        v[mp[s[i]]].push_back(i);
    }
}

int dp[401][401][401][3];

int cost(int a, int b, int c, int pos)
{
    int res = 0;
    res += max(0, a - cnt[pos][0]);
    res += max(0, b - cnt[pos][1]);
    res += max(0, c - cnt[pos][2]);
    return res;
}

void solve(void)
{
    memset(dp, 0x3f, sizeof dp);
    for (int x = 0; x < 3; x ++) dp[0][0][0][x] = 0;
    int N0 = cnt[n][0], N1 = cnt[n][1], N2 = cnt[n][2];
    for (int i = 0; i <= N0; i ++)
        for (int j = 0; j <= N1; j ++)
            for (int k = 0; k <= N2; k ++)
                for (int x = 0; x < 3; x ++)
                    if (dp[i][j][k][x] < INF)
                    {
                        if (x != 0 && i < N0)
                            minimize(dp[i + 1][j][k][0], dp[i][j][k][x] + cost(i, j, k, v[0][i]));
                        if (x != 1 && j < N1)
                            minimize(dp[i][j + 1][k][1], dp[i][j][k][x] + cost(i, j, k, v[1][j]));
                        if (x != 2 && k < N2)
                            minimize(dp[i][j][k + 1][2], dp[i][j][k][x] + cost(i, j, k, v[2][k]));
                    }
    int ans = INF;
    for (int x = 0; x < 3; x ++) minimize(ans, dp[N0][N1][N2][x]);
    cout << (ans != INF ? ans : -1);
}

int main()
{
    std::ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("mixpotions.inp", "r", stdin);
//freopen("mixpotions.out", "w", stdout);
    int test = 1;
    //cin >> test;
    while (test --)
    {
        Input();
        solve();
    }
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void Input()':
joi2019_ho_t3.cpp:52:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |         cnt[i][mp[s[i]]] ++;
      |                       ^
joi2019_ho_t3.cpp:53:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   53 |         v[mp[s[i]]].push_back(i);
      |                  ^

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