Submission #723231

#	Time	Username	Problem	Language	Result	Execution time	Memory
723231		Pring	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	134 ms	58328 KiB

joi2019_ho_t3

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

#define int long long
typedef pair<int, int> pii;
typedef vector<array<int, 3>> va;
typedef vector<va> vva;
typedef vector<vva> vvva;

const int MXN = 405;
int N, n[3], M[256], ans;
string s;
vvva dp;
vector<int> ID[3];
array<int, 3> cnt[MXN];

void init() {
    M['R'] = 0;
    M['G'] = 1;
    M['Y'] = 2;
}

int operator-(array<int, 3> arr1, array<int, 3> arr2) {
    // cout << "---" << max(0LL, arr1[0] - arr2[0]) + max(0LL, arr1[1] - arr2[1]) + max(0LL, arr1[2] - arr2[2]) << ' ';
    // return (arr1[0] + arr1[1] + arr1[2]) - (arr2[0] + arr2[1] + arr2[2]);
    return max(0LL, arr1[0] - arr2[0]) + max(0LL, arr1[1] - arr2[1]) + max(0LL, arr1[2] - arr2[2]);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    init();
    cin >> N >> s;
    {
        array<int, 3> br = {0, 0, 0};
        for (int i = 0; i < N; i++) {
            br[M[s[i]]]++;
            ID[M[s[i]]].push_back(i);
            cnt[i] = br;
        }
    }
    for (int i = 0; i < 3; i++) n[i] = ID[i].size();
    dp = vvva(n[0] + 1, vva(n[1] + 1, va(n[2] + 1)));
    for (int i = 0; i <= n[0]; i++) {
        for (int j = 0; j <= n[1]; j++) {
            for (int k = 0; k <= n[2]; k++) {
                array<int, 3> br = {i, j, k};
                // cout << i << ' ' << j << ' ' << k << endl;
                for (int l = 0; l < 3; l++) {
                    // cout << l << ' ';
                    if (i == 0 && j == 0 && k == 0) {
                        dp[i][j][k][l] = 0;
                        // cout << dp[i][j][k][l] << endl;
                        continue;
                    }
                    dp[i][j][k][l] = INT_MAX;
                    if (br[l] == 0) {
                        // cout << dp[i][j][k][l] << endl;
                        continue;
                    }
                    br[l]--;
                    for (int dl = 1; dl < 3; dl++) {
                        int tar = (l + dl) % 3;
                        // cout << 't' << tar << ' ';
                        // if (br[tar] == 0) continue;
                        dp[i][j][k][l] = min(dp[i][j][k][l], dp[br[0]][br[1]][br[2]][tar] + (cnt[ID[l][br[l]]] - br) - 1);
                        // cout << dp[i][j][k][l] << ' ';
                    }
                    // cout << dp[i][j][k][l] << endl;
                    br[l]++;
                }
            }
        }
    }
    ans = INT_MAX;
    for (int i = 0; i < 3; i++) {
        ans = min(ans, dp[n[0]][n[1]][n[2]][i]);
    } 
    cout << (ans == INT_MAX ? -1 : ans) << endl;
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:37:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |             br[M[s[i]]]++;
      |                      ^
joi2019_ho_t3.cpp:38:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |             ID[M[s[i]]].push_back(i);
      |                      ^

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