Submission #757390

#TimeUsernameProblemLanguageResultExecution timeMemory
757390drdilyorVim (BOI13_vim)C++17
1.39 / 100
429 ms524288 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 1e9;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string s;
    cin >> n >> s;

    vector memo(n, vector(n, -1));
    auto dp = [&](auto& dp, int l, int ne)->int {
        if (ne == n) return 0;
        if (memo[l][ne] !=-1) return memo[l][ne];
        vector seen(10, 0);
        int res = inf;
        int cnt = 0;
        for (int r = l+1; r < n; r++) {
            if (s[r] == 'e') {
                if (r >= ne) cnt++;
                continue;
            }
            if (seen[s[r] % 10]) continue;
            seen[s[r] % 10] = 1;
            if (cnt == 0) res = min(res, dp(dp, r, ne) + 2);
            else {
                int nne = r+1;
                while (nne <n && s[nne] != 'e') nne++;
                int cn = 0;
                for (int i = ne; i < n; i++)
                    if (s[i] == 'e') cn++;
                    else break;
                res = min(res, dp(dp, ne, nne) + 2 + (r - (ne + cn-1)) + cnt*2 - cn);
            }
        }
        return memo[l][ne] = res;
    };

    int ne = find(s.begin(), s.end(), 'e') - s.begin();
    cout << dp(dp, 0, ne)-1;
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...