Submission #1310435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310435		Born_To_Laugh	Vim (BOI13_vim)	C++17	42.50 / 100	233 ms	6812 KiB

vim

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
const int maxn = 7e4 + 10;
string s;
int n;
int a[maxn];
vector<int> jum[maxn];
map<pair<int,int>, int> mp;
int laste = INF;
int cnte = 0;
int nxtem[maxn];
void solve(){
    cin >> n >> s;
    s = "%" + s;
    vector<int> last(11, INF);

    for(int i=n; i>=1; --i){
        jum[i] = last;
        last[s[i] - 'a'] = i;
        if(s[i] == 'e'){
            if(laste == INF)laste = i;
            cnte++;
            nxtem[i] = nxtem[i + 1];
        }
        else nxtem[i] = i;
    }
    if(cnte == 0){
        cout << 0 << '\n';
        return;
    }
    
    int ans = INF;
    mp[{1, 1}] = 0;
    while(!mp.empty()){
        auto x = *mp.begin();
        mp.erase(mp.begin());
        if(x.fi.se >= laste){
            ans = min(ans, x.se);
        }
        // cout << x.fi.fi << ' ' << x.fi.se << "   :   " << x.se << '\n';
        for(int i=0; i<=10; ++i){
            if(i == 'e' - 'a')continue;
            if(jum[x.fi.fi][i] == INF)continue;
            int j = jum[x.fi.fi][i];
            int nxte = jum[x.fi.se]['e' - 'a'];
            if(j >= nxte){
                if(mp[{nxtem[nxte], j}] == 0)mp[{nxtem[nxte], j}] = INF;
                mp[{nxtem[nxte], j}] = min(mp[{nxtem[nxte], j}], x.se + 2 + j - nxte);
            }
            else{
                if(mp[{j, j}] == 0)mp[{j, j}] = INF;
                mp[{j, j}] = min(mp[{j, j}], x.se + 2);
            }
        }
    }
    cout << ans + cnte << '\n';

}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

• Subtask 1: 37.5 / 50
• Subtask 2: 5 / 10
• Subtask 3: 0 / 40