Submission #1186090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186090		patgra	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	5 / 100	1096 ms	328 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

vector<char> V = {'Y', 'R', 'G'};
map<char, int> M = { {'Y', 0}, {'R', 1}, {'G', 2} };

int n;
string s, s2;
int ans = 1e9 + 9;

void brutas(int ind) {
    if(ind == n) {
        vector<int> cnt(3, 0);
        repIn(i, s) cnt[M[i]]++;
        repIn(i, s2) cnt[M[i]]--;
        repIn(i, cnt) if(i != 0) return;
        int cost = 0;
        string sc = s;
        repIn(i, s2) {
            auto it = sc.begin();
            while(*it != i) it++, cost++;
            sc.erase(it);
        }
        ans = min(ans, cost);
        return;
    }
    rep(i, 0, 3) {
        if(ind && s2[ind - 1] == V[i]) continue;
        s2[ind] = V[i];
        brutas(ind + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> s;
    s2.resize(n);
    brutas(0);
    cout << (ans == (int)1e9 + 9 ? -1 : ans)  << eol;
}

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