Submission #757425

#	Time	Username	Problem	Language	Result	Execution time	Memory
757425		The_Samurai	Vim (BOI13_vim)	C++17	50 / 100	2082 ms	524288 KiB

vim

#include "bits/stdc++.h"

using namespace std;

int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    clock_t startTime = clock();
    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> pos(150);
    vector<int> not_e;
    for (int i = 0; i < n; i++) {
        pos[s[i]].emplace_back(i);
        if (s[i] != 'e') {
            not_e.emplace_back(i);
        }
    }
    if (pos['e'].empty()) {
        cout << 0;
        return 0;
    }
    auto cnt = [&](int l, int r, char x) {
        return upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l);
    };
    vector<vector<int>> dist(n, vector<int>(n, INF));
    auto dist_calc = [&](int l, int r) {
        int ans = INF;
        for (char x = 'a'; x <= 'z'; x++) {
            if (x == 'e' or pos[x].empty() or pos[x].back() < r) continue;
            int first = *lower_bound(pos[x].begin(), pos[x].end(), r);
            int now = cnt(l + 1, first, x) * 2;
            now += first - r;
            ans = min(ans, now);
        }
        return min(ans, dist[l][r]);
    };

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            dist[i][j] = dist_calc(i, j);
        }
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i <= k and k <= j) {
                     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    vector<vector<int>> dp(pos['e'].size(), vector<int>(pos['e'].size(), INF));
    for (int i = 0; i < dp.size(); i++) {
        // birinchi i ta 'e' ni o'chirish
        for (int j = 0; j <= i; j++) {
            // birinchi i ta 'e' ni o'chirib, j-'e' da to'xtash
            if (j == 0) {
                int now = dist[0][pos['e'][i]];
                // orasida hammasi bilan yurib chiqish
                now += pos['e'][i] - pos['e'][0];
                // 'e' larni o'chirish
                now += i + 1;
                dp[i][j] = now;
                continue;
                // bu qismi to'g'ri
            }
            for (int k = 0; k < j; k++) {
                int now = dp[j - 1][k] + dist[*lower_bound(not_e.begin(), not_e.end(), pos['e'][k])][pos['e'][i]];
                now += pos['e'][i] - pos['e'][j];
                now += i - j + 1;
                dp[i][j] = min(dp[i][j], now);
            }
        }
    }
    // i = 2, j = 2, k = 0
    cout << *min_element(dp.back().begin(), dp.back().end());


#ifdef sunnitov
    cerr << "\nTime: " << (int)((double)(clock() - startTime) / CLOCKS_PER_SEC * 1000);
#endif
}

/*
 chefeddiefedjeffeachbigagedegghehad - 0
 chefeddiefedjeffeachbigagedegghehad - 0

*/

Compilation message (stderr)

vim.cpp: In function 'int main()':
vim.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < dp.size(); i++) {
      |                     ~~^~~~~~~~~~~
vim.cpp:9:13: warning: unused variable 'startTime' [-Wunused-variable]
    9 |     clock_t startTime = clock();
      |             ^~~~~~~~~

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