Submission #757489

#	Time	Username	Problem	Language	Result	Execution time	Memory
757489		dxz05	Vim (BOI13_vim)	C++17	0 / 100	2079 ms	10064 KiB

vim

//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 7e4 + 2;

vector<int> get_dist(const string &s, int pos){
    int n = (int) s.size();

    vector<vector<int>> nxt(n);
    vector<int> last(26, 0);

    for (int i = n - 1; i >= 0; i--){
        nxt[i].assign(26, i);

        for (int j = 0; j < 26; j++){
            nxt[i][j] = last[j];
            if (j == 4) nxt[i][j] = -1;
        }

        last[s[i] - 'a'] = i;
    }

    vector<int> dp(n, 1e9);
    dp[pos] = 0;

    priority_queue<pair<int, int>> pq;
    pq.emplace(0, pos);
    vector<bool> processed(n, false);

    while (!pq.empty()){
        int i = pq.top().second;
        pq.pop();

        if (processed[i]) continue;
        processed[i] = true;

        if (i > 0 && dp[i - 1] > dp[i] + 1){
            dp[i - 1] = dp[i] + 1;
            pq.emplace(-dp[i - 1], i - 1);
        }

        for (int j = 0; j < 26; j++){
            int t = nxt[i][j];
            if (t >= 0 && dp[t] > dp[i] + 2){
                dp[t] = dp[i] + 2;
                pq.emplace(-dp[t], t);
            }
        }

    }

    return dp;
}

void solve(){
    int n; string s;
    cin >> n >> s;

    int pos = 0;
    int ans = 0;

    while (count(all(s), 'e')){
        n = (int) s.size();

        if (s[pos] == 'e'){
            ans++;
            s.erase(s.begin() + pos);
            continue;
        }

        int i = find(all(s), 'e') - s.begin();
        while (i < n && s[i] == 'e') i++;
        i--;

        ans += get_dist(s, pos)[i];
        pos = i;
    }

    cout << ans << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message (stderr)

vim.cpp: In function 'int main()':
vim.cpp:99:13: warning: unused variable 'startTime' [-Wunused-variable]
   99 |     clock_t startTime = clock();
      |             ^~~~~~~~~

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