oj.uz

Submission #445488

# Submission time Handle Problem Language Result Execution time Memory
445488 2021-07-18T09:19:40 Z lohacho Vim (BOI13_vim) C++14
100 / 100
 93 ms 80408 KB 
#include <bits/stdc++.h>
#define int long long
#define umi(x, y) (x = min(x, y))
#define uma(x, y) (x = max(x, y))
using namespace std;

int dp[70004][12][12], ns[70004];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    string in; cin >> in;
    string s;
    vector<int> must;
    int cnt = 0, ans = 0;
    for(auto&i:in){
        if(i == 'e') ++cnt;
        else{
            s += i; must.push_back(!!cnt);
            ans += cnt * 2;
            cnt = 0;
        }
    }
    n = (int)s.size();
    for(int i = 0; i < 70004; ++i) for(int j = 0; j < 12; ++j) for(int k = 0; k < 12; ++k) dp[i][j][k] = ns[i] = (int)1e9;
    for(int i = 1; i <= 11; ++i) dp[1][i][0] = 0;
    for(int i = 1; i < n; ++i){
        for(int j = 1; j <= 11; ++j){
            for(int k = 0; k <= 11; ++k){
                umi(dp[i][j][k], ns[i]);
                if(!k){
                    if(s[i] - 'a' + 1 == j){
                        umi(ns[i + 1], dp[i][j][k] + 2);
                    }
                    else{
                        if(!must[i]) umi(dp[i + 1][j][0], dp[i][j][0]);
                        for(int x = 1; x <= 11; ++x){
                           umi(dp[i + 1][j][x], dp[i][j][0] + 1);
                        }
                    }
                }
                else{
                    if(s[i] - 'a' + 1 == j && j == k){
                        umi(ns[i + 1], dp[i][j][k] + 4);
                    }
                    else if(s[i] - 'a' + 1 == j){
                        umi(dp[i + 1][k][0], dp[i][j][k] + 2);
                        for(int x = 1; x <= 11; ++x){
                           umi(dp[i + 1][x][k], dp[i][j][k] + 3);
                        }
                    }
                    else if(s[i] - 'a' + 1 == k){
                        for(int x = 1; x <= 11; ++x){
                           umi(dp[i + 1][j][x], dp[i][j][k] + 3);
                        }
                    }
                    else{
                        umi(dp[i + 1][j][k], dp[i][j][k] + 1);
                    }
                }
            }
        }
    }
    int ans2 = (int)1e9;
    for(int i = n - 1; i >= 0; --i){
        umi(ans2, dp[i][s[i] - 'a' + 1][0] + 2);
        umi(ans2, dp[i][s[i] - 'a' + 1][11] + 2);
        if(must[i]) break;
    }
    cout << ans + ans2;
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 79720 KB Output is correct
2 Correct 44 ms 79708 KB Output is correct
3 Correct 45 ms 79680 KB Output is correct
4 Correct 37 ms 79704 KB Output is correct
5 Correct 37 ms 79704 KB Output is correct
6 Correct 39 ms 79792 KB Output is correct
7 Correct 38 ms 79672 KB Output is correct
8 Correct 39 ms 79632 KB Output is correct
9 Correct 39 ms 79696 KB Output is correct
10 Correct 46 ms 79684 KB Output is correct
11 Correct 42 ms 79740 KB Output is correct
12 Correct 36 ms 79724 KB Output is correct
13 Correct 36 ms 79760 KB Output is correct
14 Correct 38 ms 79652 KB Output is correct
15 Correct 38 ms 79696 KB Output is correct
16 Correct 43 ms 79684 KB Output is correct
17 Correct 36 ms 79632 KB Output is correct
18 Correct 43 ms 79696 KB Output is correct
19 Correct 37 ms 79700 KB Output is correct
20 Correct 37 ms 79644 KB Output is correct
21 Correct 36 ms 79768 KB Output is correct
22 Correct 44 ms 79656 KB Output is correct
23 Correct 38 ms 79716 KB Output is correct
24 Correct 40 ms 79688 KB Output is correct
25 Correct 41 ms 79740 KB Output is correct
26 Correct 40 ms 79776 KB Output is correct
27 Correct 36 ms 79696 KB Output is correct
28 Correct 44 ms 79664 KB Output is correct
29 Correct 38 ms 79632 KB Output is correct
30 Correct 36 ms 79684 KB Output is correct
31 Correct 38 ms 79760 KB Output is correct
32 Correct 37 ms 79748 KB Output is correct
33 Correct 37 ms 79728 KB Output is correct
34 Correct 36 ms 79684 KB Output is correct
35 Correct 39 ms 79744 KB Output is correct
36 Correct 38 ms 79756 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 79788 KB Output is correct
2 Correct 46 ms 79812 KB Output is correct
3 Correct 39 ms 79708 KB Output is correct
4 Correct 39 ms 79760 KB Output is correct
5 Correct 39 ms 79732 KB Output is correct
6 Correct 41 ms 79788 KB Output is correct
7 Correct 47 ms 79768 KB Output is correct
8 Correct 39 ms 79812 KB Output is correct
9 Correct 42 ms 79788 KB Output is correct
10 Correct 39 ms 79800 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 80200 KB Output is correct
2 Correct 69 ms 80288 KB Output is correct
3 Correct 73 ms 80204 KB Output is correct
4 Correct 82 ms 80364 KB Output is correct
5 Correct 76 ms 80384 KB Output is correct
6 Correct 56 ms 80100 KB Output is correct
7 Correct 67 ms 80188 KB Output is correct
8 Correct 81 ms 80244 KB Output is correct
9 Correct 80 ms 80248 KB Output is correct
10 Correct 75 ms 80104 KB Output is correct
11 Correct 78 ms 80400 KB Output is correct
12 Correct 93 ms 80392 KB Output is correct
13 Correct 78 ms 80384 KB Output is correct
14 Correct 76 ms 80408 KB Output is correct
15 Correct 68 ms 80396 KB Output is correct
16 Correct 71 ms 80288 KB Output is correct
17 Correct 70 ms 80336 KB Output is correct
18 Correct 71 ms 80288 KB Output is correct
19 Correct 72 ms 80236 KB Output is correct
20 Correct 70 ms 80188 KB Output is correct