oj.uz

Submission #445487

# Submission time Handle Problem Language Result Execution time Memory
445487 2021-07-18T09:04:51 Z lohacho Vim (BOI13_vim) C++14
77.2778 / 100
 98 ms 80440 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(!must[i]){
                        umi(dp[i + 1][j][0], dp[i][j][0] + (s[i] - 'a' + 1 == j) * 2);
                    }
                    if(s[i] - 'a' + 1 == j){
                        umi(ns[i + 1], dp[i][j][k] + 2);
                    }
                    for(int x = 1; x <= 11; ++x){
                       umi(dp[i + 1][j][x], dp[i][j][0] + 1 + (s[i] - 'a' + 1 == j) * 2);
                    }
                }
                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);
                        }
                    }
                    umi(dp[i + 1][j][k], dp[i][j][k] + 1 + (s[i] - 'a' + 1 == j) * 2 + (s[i] - 'a' + 1 == k) * 2);
                }
            }
        }
    }
    int ans2 = (int)1e9;
    for(int i = n - 1; i >= 0; --i){
        umi(ans2, dp[i][s[i] - 'a' + 1][11] + 2);
        if(must[i]) break;
    }
    cout << ans + ans2;
    return 0;
}

Subtask #1
40.2777777778 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 79684 KB Output is correct
2 Correct 37 ms 79688 KB Output is correct
3 Correct 36 ms 79732 KB Output is correct
4 Correct 37 ms 79736 KB Output is correct
5 Correct 36 ms 79704 KB Output is correct
6 Correct 37 ms 79716 KB Output is correct
7 Incorrect 36 ms 79684 KB Output isn't correct
8 Correct 37 ms 79692 KB Output is correct
9 Incorrect 37 ms 79692 KB Output isn't correct
10 Correct 38 ms 79692 KB Output is correct
11 Incorrect 38 ms 79660 KB Output isn't correct
12 Correct 36 ms 79748 KB Output is correct
13 Correct 37 ms 79736 KB Output is correct
14 Correct 38 ms 79748 KB Output is correct
15 Correct 37 ms 79728 KB Output is correct
16 Correct 41 ms 79736 KB Output is correct
17 Correct 37 ms 79640 KB Output is correct
18 Correct 36 ms 79688 KB Output is correct
19 Correct 39 ms 79636 KB Output is correct
20 Correct 37 ms 79692 KB Output is correct
21 Correct 37 ms 79684 KB Output is correct
22 Correct 38 ms 79688 KB Output is correct
23 Incorrect 44 ms 79680 KB Output isn't correct
24 Incorrect 43 ms 79712 KB Output isn't correct
25 Correct 38 ms 79684 KB Output is correct
26 Correct 36 ms 79688 KB Output is correct
27 Correct 38 ms 79664 KB Output is correct
28 Correct 37 ms 79688 KB Output is correct
29 Correct 39 ms 79660 KB Output is correct
30 Correct 37 ms 79676 KB Output is correct
31 Correct 37 ms 79684 KB Output is correct
32 Correct 41 ms 79704 KB Output is correct
33 Incorrect 39 ms 79684 KB Output isn't correct
34 Correct 38 ms 79764 KB Output is correct
35 Correct 38 ms 79728 KB Output is correct
36 Incorrect 36 ms 79732 KB Output isn't correct

Subtask #2
7.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 79724 KB Output isn't correct
2 Correct 41 ms 79764 KB Output is correct
3 Correct 38 ms 79784 KB Output is correct
4 Incorrect 39 ms 79724 KB Output isn't correct
5 Correct 46 ms 79760 KB Output is correct
6 Incorrect 45 ms 79856 KB Output isn't correct
7 Correct 39 ms 79824 KB Output is correct
8 Correct 39 ms 79716 KB Output is correct
9 Correct 40 ms 79696 KB Output is correct
10 Correct 39 ms 79820 KB Output is correct

Subtask #3
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 80320 KB Output isn't correct
2 Correct 96 ms 80356 KB Output is correct
3 Correct 78 ms 80312 KB Output is correct
4 Correct 78 ms 80440 KB Output is correct
5 Correct 83 ms 80372 KB Output is correct
6 Correct 62 ms 80072 KB Output is correct
7 Incorrect 74 ms 80176 KB Output isn't correct
8 Incorrect 97 ms 80248 KB Output isn't correct
9 Incorrect 67 ms 80188 KB Output isn't correct
10 Correct 66 ms 80188 KB Output is correct
11 Correct 80 ms 80384 KB Output is correct
12 Correct 85 ms 80392 KB Output is correct
13 Correct 98 ms 80348 KB Output is correct
14 Correct 92 ms 80384 KB Output is correct
15 Correct 78 ms 80368 KB Output is correct
16 Correct 81 ms 80248 KB Output is correct
17 Incorrect 76 ms 80200 KB Output isn't correct
18 Correct 81 ms 80316 KB Output is correct
19 Correct 80 ms 80324 KB Output is correct
20 Correct 70 ms 80188 KB Output is correct