Submission #479759

#	Time	Username	Problem	Language	Result	Execution time	Memory
479759		lightseba	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	515 ms	757572 KiB

joi2019_ho_t3

// I'm a paragraph. Click here to add your own text and edit me. It’s easy. 
// Just click “Edit Text” or double click me to add your own content 
// and make changes to the font. Feel free to drag and drop me anywhere 
// you like on your page. I’m a great place for you to tell a story 
// and let your users know a little more about you.

#include <bits/stdc++.h>
using namespace std;
#define filename ""

#define pb push_back
#define mp make_pair
#define eb emplace_back
#define xx first
#define yy second
#define sz(x) ((int) size(x))
#define all(x) begin(x), end(x)
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;

const int oo = 1e7;
const int N = 400 + 1;
int dp[N][N][N][3];
int idx[3][N];
int ns[3];
int pos[3][N];
// vi pos[3];

int go(int i, int j, int k, int c) {
    bool place0 = i < ns[0];
    bool place1 = j < ns[1];
    bool place2 = k < ns[2];

    if (!place0 && !place1 && !place2)  
        return 0;

    if (dp[i][j][k][c] != -1)
        return dp[i][j][k][c];
    
    int first = oo;
    if (place0) first = min(first, pos[0][i]);
    if (place1) first = min(first, pos[1][j]);
    if (place2) first = min(first, pos[2][k]);

    place0 &= c != 0;
    place1 &= c != 1;
    place2 &= c != 2;

    int p = i + j + k;
    int ans = oo;

    if (place0) {
        int to = pos[0][i];
        int shift = max(0, j - idx[1][to]) + max(0, k - idx[2][to]);
        to += shift;
        ans = min(ans, abs(p - to) + go(i + 1, j, k, 0));
    }
    if (place1) {
        int to = pos[1][j];
        int shift = max(0, i - idx[0][to]) + max(0, k - idx[2][to]);
        to += shift;
        ans = min(ans, abs(p - to) + go(i, j + 1, k, 1));
    }
    if (place2) {
        int to = pos[2][k];
        int shift = max(0, j - idx[1][to]) + max(0, i - idx[0][to]);
        to += shift;
        ans = min(ans, abs(p - to) + go(i, j, k + 1, 2));
    }

    return dp[i][j][k][c] = ans;
}

void solve() {   
    memset(dp, -1, sizeof(dp));
    
    int n;
    string s;
    cin >> n >> s;

    ns[0] = ns[1] = ns[2] = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') pos[0][ns[0]++] = i;
        if (s[i] == 'G') pos[1][ns[1]++] = i;
        if (s[i] == 'Y') pos[2][ns[2]++] = i;

        for (int j = 0; j < 3; j++) 
            idx[j][i] = ns[j];
    }

    for (int i = ns[0]; i >= 0; i--)
        for (int j = ns[1]; j >= 0; j--)
            for (int k = ns[2]; k >= 0; k--)
                for (int c = 0; c < 3; c++)
                    go(i, j, k, c);

    int ans = min({go(0, 0, 0, 0), go(0, 0, 0, 1), go(0, 0, 0, 2)});

    if (ans >= oo)
        ans = -1;

    cout << ans << "\n";
} 

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	// freopen(filename ".in", "r", stdin); freopen(filename ".out", "w", stdout); 

	// int t; cin >> t; while (t--)
	solve();

	return 0;
}

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