oj.uz

답안 #445442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445442 2021-07-18T03:27:23 Z lohacho Vim (BOI13_vim) C++14
5.55556 / 100
 89 ms 80000 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] || 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);
                        }
                    }
                    else{
                        for(int x = 1; x <= 11; ++x){
                           umi(dp[i + 1][j][x], dp[i][j][k] + 1);
                        }
                    }
                }
                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
5.55555555556 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 79112 KB Output isn't correct
2 Incorrect 37 ms 79156 KB Output isn't correct
3 Incorrect 43 ms 79204 KB Output isn't correct
4 Incorrect 44 ms 79164 KB Output isn't correct
5 Incorrect 37 ms 79164 KB Output isn't correct
6 Incorrect 37 ms 79196 KB Output isn't correct
7 Incorrect 42 ms 79196 KB Output isn't correct
8 Correct 41 ms 79160 KB Output is correct
9 Incorrect 39 ms 79176 KB Output isn't correct
10 Incorrect 40 ms 79160 KB Output isn't correct
11 Correct 39 ms 79172 KB Output is correct
12 Correct 39 ms 79208 KB Output is correct
13 Incorrect 39 ms 79140 KB Output isn't correct
14 Incorrect 44 ms 79164 KB Output isn't correct
15 Incorrect 44 ms 79096 KB Output isn't correct
16 Incorrect 39 ms 79132 KB Output isn't correct
17 Incorrect 39 ms 79112 KB Output isn't correct
18 Incorrect 39 ms 79120 KB Output isn't correct
19 Correct 42 ms 79132 KB Output is correct
20 Incorrect 39 ms 79140 KB Output isn't correct
21 Incorrect 39 ms 79172 KB Output isn't correct
22 Incorrect 38 ms 79180 KB Output isn't correct
23 Incorrect 41 ms 79220 KB Output isn't correct
24 Incorrect 38 ms 79112 KB Output isn't correct
25 Incorrect 43 ms 79172 KB Output isn't correct
26 Incorrect 42 ms 79188 KB Output isn't correct
27 Incorrect 36 ms 79092 KB Output isn't correct
28 Incorrect 38 ms 79212 KB Output isn't correct
29 Incorrect 39 ms 79112 KB Output isn't correct
30 Incorrect 42 ms 79160 KB Output isn't correct
31 Incorrect 41 ms 79204 KB Output isn't correct
32 Incorrect 43 ms 79104 KB Output isn't correct
33 Incorrect 40 ms 79172 KB Output isn't correct
34 Incorrect 42 ms 79200 KB Output isn't correct
35 Incorrect 38 ms 79172 KB Output isn't correct
36 Incorrect 46 ms 79180 KB Output isn't correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 79208 KB Output isn't correct
2 Incorrect 41 ms 79156 KB Output isn't correct
3 Incorrect 40 ms 79212 KB Output isn't correct
4 Incorrect 45 ms 79164 KB Output isn't correct
5 Incorrect 47 ms 79204 KB Output isn't correct
6 Incorrect 43 ms 79276 KB Output isn't correct
7 Incorrect 46 ms 79228 KB Output isn't correct
8 Incorrect 43 ms 79212 KB Output isn't correct
9 Incorrect 44 ms 79260 KB Output isn't correct
10 Incorrect 44 ms 79204 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 79744 KB Output isn't correct
2 Incorrect 86 ms 79804 KB Output isn't correct
3 Incorrect 83 ms 79800 KB Output isn't correct
4 Incorrect 80 ms 79956 KB Output isn't correct
5 Incorrect 87 ms 79880 KB Output isn't correct
6 Incorrect 67 ms 79596 KB Output isn't correct
7 Incorrect 77 ms 79724 KB Output isn't correct
8 Incorrect 83 ms 79808 KB Output isn't correct
9 Incorrect 73 ms 79716 KB Output isn't correct
10 Incorrect 68 ms 79708 KB Output isn't correct
11 Incorrect 82 ms 79888 KB Output isn't correct
12 Incorrect 86 ms 80000 KB Output isn't correct
13 Incorrect 87 ms 79936 KB Output isn't correct
14 Incorrect 89 ms 79996 KB Output isn't correct
15 Incorrect 80 ms 79872 KB Output isn't correct
16 Incorrect 82 ms 79820 KB Output isn't correct
17 Incorrect 80 ms 79808 KB Output isn't correct
18 Incorrect 81 ms 79724 KB Output isn't correct
19 Incorrect 77 ms 79796 KB Output isn't correct
20 Incorrect 70 ms 79716 KB Output isn't correct