oj.uz

Submission #445446

# Submission time Handle Problem Language Result Execution time Memory
445446 2021-07-18T03:44:47 Z lohacho Vim (BOI13_vim) C++14
36.1667 / 100
 99 ms 79912 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];

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;
        }
    }
    while((int)must.size() && !must.back()){
        must.pop_back(); s.pop_back();
    }
    must.push_back(0), s += 'a' + 10;
    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] = (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){
                if(!k){
                    if(!must[i]){
                        umi(dp[i + 1][j][k], dp[i][j][k] + (s[i] - 'a' + 1 == j) * 2);
                    }
                    if(s[i] - 'a' + 1 == j){
                        for(int x = 1; x <= 11; ++x){
                           umi(dp[i + 1][x][k], dp[i][j][k] + (s[i] - 'a' + 1 == j) * 2);
                        }
                    }
                    for(int x = 1; x <= 11; ++x){
                       umi(dp[i + 1][j][x], dp[i][j][k] + 1 + (s[i] - 'a' + 1 == j) * 2);
                    }
                }
                else{
                    if(s[i] - 'a' + 1 == j){
                        umi(dp[i + 1][k][0], dp[i][j][k] + 2 + (s[i] - 'a' + 1 == k) * 2);
                        for(int x = 1; x <= 11; ++x){
                           umi(dp[i + 1][x][k], dp[i][j][k] + 3 + (s[i] - 'a' + 1 == k) * 2);
                        }
                    }
                    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 + (s[i] - 'a' + 1 == j) * 2);
                        }
                    }
                    else{
                        umi(dp[i + 1][j][k], dp[i][j][k] + 1 + (s[i] - 'a' + 1 == k) * 2);
                    }
                }
            }
        }
    }
    cout << ans + dp[n - 1][s[n - 2] - 'a' + 1][11] - 1;
    return 0;
}

Subtask #1
29.1666666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 79096 KB Output is correct
2 Incorrect 42 ms 79144 KB Output isn't correct
3 Incorrect 45 ms 79176 KB Output isn't correct
4 Incorrect 43 ms 79124 KB Output isn't correct
5 Correct 42 ms 79176 KB Output is correct
6 Incorrect 41 ms 79172 KB Output isn't correct
7 Incorrect 41 ms 79216 KB Output isn't correct
8 Correct 46 ms 79116 KB Output is correct
9 Correct 43 ms 79120 KB Output is correct
10 Correct 42 ms 79140 KB Output is correct
11 Correct 41 ms 79228 KB Output is correct
12 Correct 40 ms 79136 KB Output is correct
13 Correct 41 ms 79144 KB Output is correct
14 Incorrect 41 ms 79116 KB Output isn't correct
15 Incorrect 40 ms 79104 KB Output isn't correct
16 Incorrect 40 ms 79156 KB Output isn't correct
17 Correct 45 ms 79192 KB Output is correct
18 Incorrect 40 ms 79168 KB Output isn't correct
19 Correct 47 ms 79096 KB Output is correct
20 Incorrect 40 ms 79172 KB Output isn't correct
21 Incorrect 46 ms 79096 KB Output isn't correct
22 Correct 40 ms 79088 KB Output is correct
23 Incorrect 39 ms 79116 KB Output isn't correct
24 Correct 46 ms 79136 KB Output is correct
25 Correct 40 ms 79172 KB Output is correct
26 Correct 42 ms 79200 KB Output is correct
27 Correct 39 ms 79156 KB Output is correct
28 Incorrect 40 ms 79100 KB Output isn't correct
29 Correct 47 ms 79124 KB Output is correct
30 Correct 61 ms 79192 KB Output is correct
31 Correct 42 ms 79180 KB Output is correct
32 Correct 39 ms 79088 KB Output is correct
33 Correct 40 ms 79176 KB Output is correct
34 Correct 38 ms 79192 KB Output is correct
35 Incorrect 46 ms 79104 KB Output isn't correct
36 Incorrect 44 ms 79172 KB Output isn't correct

Subtask #2
1.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 79172 KB Output isn't correct
2 Incorrect 43 ms 79172 KB Output isn't correct
3 Incorrect 41 ms 79168 KB Output isn't correct
4 Incorrect 42 ms 79180 KB Output isn't correct
5 Incorrect 43 ms 79204 KB Output isn't correct
6 Correct 46 ms 79164 KB Output is correct
7 Incorrect 43 ms 79168 KB Output isn't correct
8 Incorrect 42 ms 79180 KB Output isn't correct
9 Incorrect 44 ms 79176 KB Output isn't correct
10 Incorrect 42 ms 79172 KB Output isn't correct

Subtask #3
6.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 79672 KB Output isn't correct
2 Incorrect 90 ms 79712 KB Output isn't correct
3 Correct 89 ms 79760 KB Output is correct
4 Incorrect 87 ms 79776 KB Output isn't correct
5 Incorrect 98 ms 79880 KB Output isn't correct
6 Incorrect 67 ms 79548 KB Output isn't correct
7 Incorrect 98 ms 79716 KB Output isn't correct
8 Incorrect 88 ms 79764 KB Output isn't correct
9 Incorrect 75 ms 79596 KB Output isn't correct
10 Incorrect 71 ms 79560 KB Output isn't correct
11 Incorrect 88 ms 79784 KB Output isn't correct
12 Incorrect 96 ms 79808 KB Output isn't correct
13 Correct 99 ms 79816 KB Output is correct
14 Incorrect 92 ms 79912 KB Output isn't correct
15 Incorrect 83 ms 79856 KB Output isn't correct
16 Incorrect 91 ms 79716 KB Output isn't correct
17 Incorrect 85 ms 79748 KB Output isn't correct
18 Correct 99 ms 79756 KB Output is correct
19 Incorrect 84 ms 79704 KB Output isn't correct
20 Incorrect 76 ms 79676 KB Output isn't correct