Submission #479761

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

void solve() {       
    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++) {
                        bool place0 = i < ns[0];
                        bool place1 = j < ns[1];
                        bool place2 = k < ns[2];

                        if (!place0 && !place1 && !place2) {
                            dp[i][j][k][c] = 0;
                            continue;
                        }

                        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) + dp[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) + dp[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) + dp[i][j][k + 1][2]);
                        }

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

    int ans = min(dp[0][0][0][0], dp[0][0][0][1]);

    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: 25 / 25