oj.uz

답안 #445460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445460 2021-07-18T06:06:25 Z lohacho Vim (BOI13_vim) C++14
18.6667 / 100
 102 ms 80512 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;
        }
    }
    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] = 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){
                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][0], dp[i][j][0] + 2);
                        }
                        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][k] + 1 + (s[i] - 'a' + 1 == j) * 2);
                    }
                }
                else{
                    umi(dp[i][j][k], ns[i]);
                    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);
                        }
                        if(j == k){
                            umi(ns[i + 1], dp[i][j][k] + 5);
                        }
                    }
                    if(s[i] - 'a' + 1 == k){
                        for(int x = 0; x <= 11; ++x){
                           umi(dp[i + 1][j][x], dp[i][j][k] + 3 + (s[i] - 'a' + 1 == j) * 2);
                        }
                    }
                    umi(dp[i + 1][j][k], dp[i][j][k] + 1 + (s[i] - 'a' + 1 == j) * 2 + (s[i] - 'a' + 1 == k) * 2);
                }
            }
        }
    }
    cout << ans + dp[n - 1][s[n - 2] - 'a' + 1][11] - 1;
    return 0;
}

Subtask #1
16.6666666667 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 79684 KB Output is correct
2 Incorrect 37 ms 79752 KB Output isn't correct
3 Incorrect 37 ms 79724 KB Output isn't correct
4 Correct 38 ms 79708 KB Output is correct
5 Correct 38 ms 79644 KB Output is correct
6 Incorrect 38 ms 79692 KB Output isn't correct
7 Incorrect 37 ms 79668 KB Output isn't correct
8 Incorrect 38 ms 79696 KB Output isn't correct
9 Incorrect 38 ms 79720 KB Output isn't correct
10 Incorrect 39 ms 79664 KB Output isn't correct
11 Incorrect 40 ms 79712 KB Output isn't correct
12 Incorrect 38 ms 79684 KB Output isn't correct
13 Correct 38 ms 79744 KB Output is correct
14 Incorrect 37 ms 79644 KB Output isn't correct
15 Incorrect 38 ms 79648 KB Output isn't correct
16 Incorrect 37 ms 79684 KB Output isn't correct
17 Incorrect 40 ms 79808 KB Output isn't correct
18 Correct 41 ms 79716 KB Output is correct
19 Correct 39 ms 79740 KB Output is correct
20 Incorrect 39 ms 79700 KB Output isn't correct
21 Correct 38 ms 79668 KB Output is correct
22 Correct 38 ms 79636 KB Output is correct
23 Incorrect 38 ms 79688 KB Output isn't correct
24 Incorrect 39 ms 79660 KB Output isn't correct
25 Incorrect 40 ms 79684 KB Output isn't correct
26 Incorrect 38 ms 79648 KB Output isn't correct
27 Correct 39 ms 79740 KB Output is correct
28 Incorrect 39 ms 79708 KB Output isn't correct
29 Correct 38 ms 79752 KB Output is correct
30 Incorrect 38 ms 79684 KB Output isn't correct
31 Correct 39 ms 79692 KB Output is correct
32 Incorrect 38 ms 79732 KB Output isn't correct
33 Incorrect 37 ms 79760 KB Output isn't correct
34 Incorrect 38 ms 79760 KB Output isn't correct
35 Correct 38 ms 79676 KB Output is correct
36 Incorrect 38 ms 79684 KB Output isn't correct

Subtask #2
2.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 79708 KB Output is correct
2 Incorrect 48 ms 79720 KB Output isn't correct
3 Incorrect 40 ms 79776 KB Output isn't correct
4 Correct 40 ms 79684 KB Output is correct
5 Incorrect 40 ms 79820 KB Output isn't correct
6 Incorrect 41 ms 79704 KB Output isn't correct
7 Incorrect 43 ms 79816 KB Output isn't correct
8 Incorrect 41 ms 79780 KB Output isn't correct
9 Incorrect 40 ms 79800 KB Output isn't correct
10 Incorrect 41 ms 79812 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 80316 KB Output isn't correct
2 Incorrect 88 ms 80244 KB Output isn't correct
3 Incorrect 89 ms 80316 KB Output isn't correct
4 Incorrect 92 ms 80496 KB Output isn't correct
5 Incorrect 102 ms 80492 KB Output isn't correct
6 Incorrect 64 ms 80192 KB Output isn't correct
7 Incorrect 80 ms 80284 KB Output isn't correct
8 Incorrect 89 ms 80292 KB Output isn't correct
9 Incorrect 75 ms 80224 KB Output isn't correct
10 Incorrect 74 ms 80276 KB Output isn't correct
11 Incorrect 89 ms 80472 KB Output isn't correct
12 Incorrect 95 ms 80472 KB Output isn't correct
13 Incorrect 95 ms 80508 KB Output isn't correct
14 Incorrect 100 ms 80512 KB Output isn't correct
15 Incorrect 86 ms 80384 KB Output isn't correct
16 Incorrect 90 ms 80324 KB Output isn't correct
17 Incorrect 88 ms 80316 KB Output isn't correct
18 Incorrect 89 ms 80408 KB Output isn't correct
19 Incorrect 86 ms 80316 KB Output isn't correct
20 Incorrect 81 ms 80276 KB Output isn't correct