Submission #1333555

#TimeUsernameProblemLanguageResultExecution timeMemory
1333555penguin133Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
5 / 100
507 ms1040432 KiB
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
int n;
char a[405];
int b[405];
vector <int> v[4];

int memo[405][405][405][4];

int dp(int x, int r, int g, int l) {
    if (x == n + 1) return 0;
    if (memo[x][r][g][l] != -1) return memo[x][r][g][l];
    //cerr << x << ' ' << r << ' ' << g << ' ' << l << '\n';
    int b = x - r - g - 1;
    int ans = 1e9;
    for (int i = 1; i <= 3; i++) {
        if (i == l) continue;
        if (i == 1 && r == sz(v[1])) continue;
        if (i == 2 && g == sz(v[2])) continue;
        if (i == 3 && b == sz(v[3])) continue;
        int pos;
        if (i == 1) {
            pos = v[1][r];
            int idx = upper_bound(v[2].begin(), v[2].end(), pos) - v[2].begin();
            int idx2 = upper_bound(v[3].begin(), v[3].end(), pos) - v[3].begin();
            //cerr << idx << ' ' << idx2 << '\n';
            pos += max(0, g - idx) + max(0, b - idx2);
            ans = min(ans, pos - x + dp(x + 1, r + 1, g, 1));
        }
        else if (i == 2) {
            pos = v[2][g];
            int idx = upper_bound(v[1].begin(), v[1].end(), pos) - v[1].begin();
            int idx2 = upper_bound(v[3].begin(), v[3].end(), pos) - v[3].begin();
            pos += max(0, r - idx) + max(0, b - idx2);
            ans = min(ans, pos - x + dp(x + 1, r, g + 1, 2));
        }
        else {
            pos = v[3][b];
            int idx = upper_bound(v[2].begin(), v[2].end(), pos) - v[2].begin();
            int idx2 = upper_bound(v[1].begin(), v[1].end(), pos) - v[1].begin();
            pos += max(0, g - idx) + max(0, r - idx2);
            ans = min(ans, pos - x + dp(x + 1, r, g, 3));
        }
        assert(pos>=x);
    }
    return memo[x][r][g][l] = ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 'R')b[i] = 1;
        else if (a[i] == 'G') b[i] = 2;
        else b[i] = 3;
        v[b[i]].push_back(i);
    }
    memset(memo, -1, sizeof(memo));
    int res = dp(1, 0, 0, 0);
    cout << (res==1e9?-1:res);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...