Submission #757414

#	Time	Username	Problem	Language	Result	Execution time	Memory
757414		drdilyor	Vim (BOI13_vim)	C++17	11.11 / 100	2085 ms	524288 KiB

vim

#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 t;
    cin >> n >> t;
    vector<int> e;
    string s;
    for (char c : t) {
        if (c != 'e') {
            s += c;
            e.push_back(0);
        } else {
            e.back()++;
        }
    }
    n = s.size();

    auto sum =[&](int l, int r) {
        ll s = 0;
        for (;l <= r; l++)
            s += e[l];
        return s;
    };
    vector memo(n, vector(n, -1));
    auto dp = [&](auto& dp, int i, int ne)->int {
        if (ne == n) return 0;
        int& res = memo[i][ne];
        if (res!=-1) return res;
        res = inf;
        set<char> seen;
        for (int j = i+1; j < n; j++) {
            if (seen.count(s[j])) continue;
            seen.insert(s[j]);
            int nne = j;
            while (nne < n && e[nne] == 0) nne++;
            int dist = j - ne;
            int ec = sum(ne, j-1);
            res = min(res, dp(dp, ne, nne) + max(0, dist) + max(0, ec * 2 - 1) + 2);
        }
        //cout << i << ' ' << ne << ' ' << res << '\n';
        return res;
    };

    int ne = 0;
    while (ne < n && e[ne] == 0) ne++;
    cout << dp(dp, 0, ne) << '\n';
    return 0;
}

• Subtask 1: 11.11111111111111 / 50
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40