답안 #757416

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
757416 2023-06-13T07:16:30 Z The_Samurai Vim (BOI13_vim) C++17
22.2222 / 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);
    };
    auto dist = [&](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 ans;
    };
    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:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < dp.size(); i++) {
      |                     ~~^~~~~~~~~~~
vim.cpp:9:13: warning: unused variable 'startTime' [-Wunused-variable]
    9 |     clock_t startTime = clock();
      |             ^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 712 ms 596 KB Output is correct
2 Incorrect 156 ms 436 KB Output isn't correct
3 Incorrect 116 ms 412 KB Output isn't correct
4 Correct 198 ms 424 KB Output is correct
5 Correct 249 ms 340 KB Output is correct
6 Incorrect 615 ms 536 KB Output isn't correct
7 Incorrect 396 ms 484 KB Output isn't correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 743 ms 612 KB Output is correct
14 Incorrect 147 ms 428 KB Output isn't correct
15 Incorrect 109 ms 412 KB Output isn't correct
16 Incorrect 145 ms 440 KB Output isn't correct
17 Correct 179 ms 340 KB Output is correct
18 Incorrect 159 ms 412 KB Output isn't correct
19 Incorrect 150 ms 420 KB Output isn't correct
20 Correct 165 ms 340 KB Output is correct
21 Correct 191 ms 420 KB Output is correct
22 Correct 263 ms 460 KB Output is correct
23 Incorrect 59 ms 340 KB Output isn't correct
24 Incorrect 51 ms 340 KB Output isn't correct
25 Incorrect 62 ms 364 KB Output isn't correct
26 Correct 92 ms 340 KB Output is correct
27 Correct 357 ms 468 KB Output is correct
28 Incorrect 586 ms 468 KB Output isn't correct
29 Incorrect 374 ms 480 KB Output isn't correct
30 Incorrect 84 ms 340 KB Output isn't correct
31 Incorrect 60 ms 356 KB Output isn't correct
32 Incorrect 84 ms 368 KB Output isn't correct
33 Incorrect 108 ms 340 KB Output isn't correct
34 Correct 282 ms 452 KB Output is correct
35 Incorrect 456 ms 492 KB Output isn't correct
36 Incorrect 392 ms 480 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2079 ms 37660 KB Time limit exceeded
2 Execution timed out 2073 ms 22148 KB Time limit exceeded
3 Execution timed out 2089 ms 8788 KB Time limit exceeded
4 Execution timed out 2077 ms 37716 KB Time limit exceeded
5 Execution timed out 2087 ms 19028 KB Time limit exceeded
6 Execution timed out 2080 ms 7764 KB Time limit exceeded
7 Execution timed out 2081 ms 27756 KB Time limit exceeded
8 Execution timed out 2066 ms 26196 KB Time limit exceeded
9 Execution timed out 2041 ms 22100 KB Time limit exceeded
10 Execution timed out 2081 ms 19452 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Runtime error 194 ms 524288 KB Execution killed with signal 9
2 Runtime error 197 ms 524288 KB Execution killed with signal 9
3 Runtime error 195 ms 524288 KB Execution killed with signal 9
4 Runtime error 195 ms 524288 KB Execution killed with signal 9
5 Runtime error 192 ms 524288 KB Execution killed with signal 9
6 Runtime error 207 ms 524288 KB Execution killed with signal 9
7 Runtime error 198 ms 524288 KB Execution killed with signal 9
8 Runtime error 189 ms 524288 KB Execution killed with signal 9
9 Runtime error 196 ms 524288 KB Execution killed with signal 9
10 Runtime error 196 ms 524288 KB Execution killed with signal 9
11 Runtime error 222 ms 524288 KB Execution killed with signal 9
12 Runtime error 193 ms 524288 KB Execution killed with signal 9
13 Runtime error 210 ms 524288 KB Execution killed with signal 9
14 Runtime error 195 ms 524288 KB Execution killed with signal 9
15 Runtime error 197 ms 524288 KB Execution killed with signal 9
16 Runtime error 203 ms 524288 KB Execution killed with signal 9
17 Runtime error 188 ms 524288 KB Execution killed with signal 9
18 Runtime error 184 ms 524288 KB Execution killed with signal 9
19 Runtime error 211 ms 524288 KB Execution killed with signal 9
20 Runtime error 243 ms 524288 KB Execution killed with signal 9