제출 #1181361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181361		anteknne	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	209 ms	383376 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

string s;

const int MAXN = 400 + 17;
vector<int> v;
int dp[MAXN][MAXN][MAXN][3];
int spref[MAXN][3];
int gdzie[MAXN][3];
int cnt[3];

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n >> s;

    s = "#" + s;

    v.pb(-1);

    memset(gdzie[0], -1, sizeof(gdzie[0]));
    memset(gdzie[1], -1, sizeof(gdzie[1]));
    memset(gdzie[2], -1, sizeof(gdzie[2]));

    for (int i = 1; i <= n; i ++) {
        if (s[i] == 'R') {
            v.pb(0);
        } else if (s[i] == 'G') {
            v.pb(1);
        } else {
            v.pb(2);
        }
        for (int k = 0; k < 3; k ++) {
            spref[i][k] = spref[i - 1][k];
        }

        spref[i][v[i]] ++;
        cnt[v[i]] ++;
        gdzie[cnt[v[i]]][v[i]] = i;

        //cout << cnt[v[i]] << " " << v[i] << ": " << i << "\n";

    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= i; j ++) {
            for (int k = 0; k <= i - j; k ++) {
                for (int l = 0; l < 3; l ++) {
                    dp[i][j][k][l] = INT_MAX;
                }
            }
        }
    }





    for (int i = 0; i <= n - 1; i ++) {
        for (int j = 0; j <= i; j ++) {
            for (int k = 0; k <= i - j; k ++) {
                int l = i - j - k;
                //dp[i + 1][j + 1][k][0] = min(dp[i][j][k][1])

                //DODAJ 0

                int x = gdzie[j + 1][0];
                if (x != -1 && min(dp[i][j][k][1], dp[i][j][k][2]) != INT_MAX) {
                    x += max(0, k - spref[x][1]) + max(0, l - spref[x][2]);
                    dp[i + 1][j + 1][k][0] = min(dp[i + 1][j + 1][k][0], min(dp[i][j][k][1], dp[i][j][k][2]) + max(0, x - (i + 1)));
                }

                //DODAJ 1
                x = gdzie[k + 1][1];
                if (x != -1 && min(dp[i][j][k][0], dp[i][j][k][2]) != INT_MAX) {
                    x += max(0, j - spref[x][0]) + max(0, l - spref[x][2]);
                    dp[i + 1][j][k + 1][1] = min(dp[i + 1][j][k + 1][1], min(dp[i][j][k][0], dp[i][j][k][2]) + max(0, x - (i + 1)));
                }


                //DODAJ 2
                x = gdzie[l + 1][2];
                if (x != -1 && min(dp[i][j][k][0], dp[i][j][k][1]) != INT_MAX) {
                    x += max(0, j - spref[x][0]) + max(0, k - spref[x][1]);
                    dp[i + 1][j][k][2] = min(dp[i + 1][j][k][2], min(dp[i][j][k][0], dp[i][j][k][1]) + max(0, x - (i + 1)));
                }
            }
        }
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= i; j ++) {
            for (int k = 0; k <= i - j; k ++) {
                for (int l = 0; l < 3; l ++) {
                    //cout << i << " " << j << " " << k << " " << l << ": " << dp[i][j][k][l] << "\n";
                }
            }
        }
    }

    int minn = INT_MAX;

    for (int l = 0; l < 3; l ++) {
        minn = min(minn, dp[n][spref[n][0]][spref[n][1]][l]);
    }

    if (minn == INT_MAX) {
        cout << -1 << "\n";
    } else {
        cout << minn << "\n";
    }



    return 0;
}

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