oj.uz

답안 #445484

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445484 2021-07-18T08:55:10 Z lohacho Vim (BOI13_vim) C++14
33.7778 / 100
 109 ms 80592 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){
                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){
                        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][0] + 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 = 1; 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);
                }
            }
        }
    }
    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
27.7777777778 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 79684 KB Output is correct
2 Incorrect 42 ms 79740 KB Output isn't correct
3 Incorrect 42 ms 79772 KB Output isn't correct
4 Correct 43 ms 79640 KB Output is correct
5 Correct 42 ms 79704 KB Output is correct
6 Incorrect 43 ms 79684 KB Output isn't correct
7 Incorrect 43 ms 79636 KB Output isn't correct
8 Correct 42 ms 79684 KB Output is correct
9 Incorrect 52 ms 79696 KB Output isn't correct
10 Correct 49 ms 79744 KB Output is correct
11 Incorrect 42 ms 79672 KB Output isn't correct
12 Correct 42 ms 79628 KB Output is correct
13 Correct 43 ms 79708 KB Output is correct
14 Incorrect 42 ms 79748 KB Output isn't correct
15 Incorrect 42 ms 79696 KB Output isn't correct
16 Incorrect 42 ms 79684 KB Output isn't correct
17 Correct 43 ms 79684 KB Output is correct
18 Incorrect 43 ms 79700 KB Output isn't correct
19 Correct 49 ms 79736 KB Output is correct
20 Correct 42 ms 79688 KB Output is correct
21 Correct 43 ms 79676 KB Output is correct
22 Correct 43 ms 79684 KB Output is correct
23 Incorrect 45 ms 79672 KB Output isn't correct
24 Incorrect 44 ms 79676 KB Output isn't correct
25 Correct 43 ms 79712 KB Output is correct
26 Correct 43 ms 79752 KB Output is correct
27 Correct 42 ms 79684 KB Output is correct
28 Incorrect 43 ms 79736 KB Output isn't correct
29 Correct 42 ms 79644 KB Output is correct
30 Correct 43 ms 79696 KB Output is correct
31 Correct 42 ms 79712 KB Output is correct
32 Correct 43 ms 79740 KB Output is correct
33 Incorrect 41 ms 79696 KB Output isn't correct
34 Correct 43 ms 79752 KB Output is correct
35 Incorrect 42 ms 79636 KB Output isn't correct
36 Incorrect 41 ms 79720 KB Output isn't correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 79696 KB Output isn't correct
2 Incorrect 53 ms 79796 KB Output isn't correct
3 Incorrect 45 ms 79740 KB Output isn't correct
4 Incorrect 44 ms 79748 KB Output isn't correct
5 Incorrect 45 ms 79832 KB Output isn't correct
6 Incorrect 46 ms 79724 KB Output isn't correct
7 Incorrect 46 ms 79776 KB Output isn't correct
8 Incorrect 46 ms 79748 KB Output isn't correct
9 Incorrect 45 ms 79752 KB Output isn't correct
10 Incorrect 45 ms 79812 KB Output isn't correct

Subtask #3
6.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 97 ms 80312 KB Output isn't correct
2 Incorrect 105 ms 80296 KB Output isn't correct
3 Correct 101 ms 80316 KB Output is correct
4 Incorrect 94 ms 80392 KB Output isn't correct
5 Incorrect 101 ms 80512 KB Output isn't correct
6 Incorrect 70 ms 80320 KB Output isn't correct
7 Incorrect 86 ms 80220 KB Output isn't correct
8 Incorrect 92 ms 80364 KB Output isn't correct
9 Incorrect 79 ms 80184 KB Output isn't correct
10 Incorrect 78 ms 80164 KB Output isn't correct
11 Incorrect 95 ms 80500 KB Output isn't correct
12 Incorrect 98 ms 80508 KB Output isn't correct
13 Correct 100 ms 80592 KB Output is correct
14 Incorrect 109 ms 80472 KB Output isn't correct
15 Incorrect 88 ms 80384 KB Output isn't correct
16 Incorrect 96 ms 80420 KB Output isn't correct
17 Incorrect 92 ms 80380 KB Output isn't correct
18 Correct 96 ms 80316 KB Output is correct
19 Incorrect 96 ms 80316 KB Output isn't correct
20 Incorrect 81 ms 80288 KB Output isn't correct