oj.uz

Submission #757425

# Submission time Handle Problem Language Result Execution time Memory
757425 2023-06-13T07:27:07 Z The_Samurai Vim (BOI13_vim) C++17
50 / 100
 2000 ms 524288 KB 
#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

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 1576 KB Output is correct
2 Correct 107 ms 1120 KB Output is correct
3 Correct 70 ms 972 KB Output is correct
4 Correct 88 ms 1000 KB Output is correct
5 Correct 92 ms 1132 KB Output is correct
6 Correct 154 ms 1440 KB Output is correct
7 Correct 144 ms 1440 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 184 ms 1568 KB Output is correct
14 Correct 101 ms 1236 KB Output is correct
15 Correct 71 ms 956 KB Output is correct
16 Correct 96 ms 1092 KB Output is correct
17 Correct 131 ms 1272 KB Output is correct
18 Correct 78 ms 952 KB Output is correct
19 Correct 57 ms 844 KB Output is correct
20 Correct 68 ms 972 KB Output is correct
21 Correct 88 ms 1000 KB Output is correct
22 Correct 100 ms 1132 KB Output is correct
23 Correct 122 ms 1272 KB Output is correct
24 Correct 101 ms 1112 KB Output is correct
25 Correct 93 ms 1088 KB Output is correct
26 Correct 108 ms 1188 KB Output is correct
27 Correct 129 ms 1468 KB Output is correct
28 Correct 154 ms 1484 KB Output is correct
29 Correct 162 ms 1436 KB Output is correct
30 Correct 123 ms 1244 KB Output is correct
31 Correct 95 ms 1080 KB Output is correct
32 Correct 118 ms 1236 KB Output is correct
33 Correct 132 ms 1248 KB Output is correct
34 Correct 108 ms 1236 KB Output is correct
35 Correct 112 ms 1248 KB Output is correct
36 Correct 168 ms 1440 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 95872 KB Time limit exceeded
2 Execution timed out 2077 ms 98380 KB Time limit exceeded
3 Execution timed out 2069 ms 31060 KB Time limit exceeded
4 Execution timed out 2071 ms 95836 KB Time limit exceeded
5 Execution timed out 2053 ms 95732 KB Time limit exceeded
6 Execution timed out 2082 ms 97868 KB Time limit exceeded
7 Execution timed out 2061 ms 97056 KB Time limit exceeded
8 Execution timed out 2073 ms 94452 KB Time limit exceeded
9 Execution timed out 2074 ms 98380 KB Time limit exceeded
10 Execution timed out 2076 ms 98372 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 197 ms 524288 KB Execution killed with signal 9
2 Runtime error 197 ms 524288 KB Execution killed with signal 9
3 Runtime error 184 ms 524288 KB Execution killed with signal 9
4 Runtime error 187 ms 524288 KB Execution killed with signal 9
5 Runtime error 189 ms 524288 KB Execution killed with signal 9
6 Runtime error 238 ms 524288 KB Execution killed with signal 9
7 Runtime error 194 ms 524288 KB Execution killed with signal 9
8 Runtime error 198 ms 524288 KB Execution killed with signal 9
9 Runtime error 196 ms 524288 KB Execution killed with signal 9
10 Runtime error 195 ms 524288 KB Execution killed with signal 9
11 Runtime error 203 ms 524288 KB Execution killed with signal 9
12 Runtime error 196 ms 524288 KB Execution killed with signal 9
13 Runtime error 195 ms 524288 KB Execution killed with signal 9
14 Runtime error 213 ms 524288 KB Execution killed with signal 9
15 Runtime error 205 ms 524288 KB Execution killed with signal 9
16 Runtime error 219 ms 524288 KB Execution killed with signal 9
17 Runtime error 196 ms 524288 KB Execution killed with signal 9
18 Runtime error 194 ms 524288 KB Execution killed with signal 9
19 Runtime error 212 ms 524288 KB Execution killed with signal 9
20 Runtime error 197 ms 524288 KB Execution killed with signal 9