oj.uz

Submission #63285

# Submission time Handle Problem Language Result Execution time Memory
63285 2018-08-01T08:37:28 Z 강태규(#1831) Vim (BOI13_vim) C++11
1.38889 / 100
 77 ms 23128 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
char in[70001];
int str[70001];
int ch[70001];

const int inf = 1e8;
int dp1[70001][10];
int dp2[70001][10][10];

void setMin(int &x, int y) {
    if (x > y) x = y;
}

int main() {
    scanf("%*d%s", in);
    int er = 0;
    for (int i = 0, fs = 0; in[i]; ++i) {
        if (in[i] == 'e') {
            er += 2;
            fs = 1;
        }
        else {
            if (fs) ch[n] = 1, fs = 0;
            str[n] = in[i] - 'a';
            if (in[i] > 'e') --str[n];
            ++n;
        }
    }
    str[n] = 9;
    for (int i = 0; i < 10; ++i) {
        dp1[0][i] = inf;
        for (int j = 0; j < 10; ++j) {
            dp2[0][i][j] = inf;
        }
    }
    dp1[0][str[0]] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 10; ++j) {
            dp1[i][j] = inf;
            if (j != str[i] && !ch[i]) setMin(dp1[i][j], dp1[i - 1][j]);
            if (j != str[i]) setMin(dp1[i][j], dp2[i - 1][j][str[i]]);
            setMin(dp1[i][j], dp1[i - 1][str[i]] + 2);
            setMin(dp1[i][j], dp2[i - 1][str[i]][str[i]] + 2);
            
            for (int k = 0; k < 10; ++k) {
                dp2[i][j][k] = inf;
                setMin(dp2[i][j][k], dp1[i - 1][str[i]] + 5);
                setMin(dp2[i][j][k], dp2[i - 1][str[i]][str[i]] + 5);
                if (j != str[i]) {
                    setMin(dp2[i][j][k], dp1[i - 1][j] + 3);
                    setMin(dp2[i][j][k], dp2[i - 1][j][str[i]] + 3);
                }
                if (k != str[i]) {
                    setMin(dp2[i][j][k], dp2[i - 1][str[i]][k] + 3);
                }
                if (j != str[i] && k != str[i])
                    setMin(dp2[i][j][k], dp2[i - 1][j][k] + 1);
            }
        }
    }
    printf("%d\n", dp1[n][9] + er - 2);
	return 0;
}

Compilation message

vim.cpp: In function 'int main()':
vim.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%*d%s", in);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
1.38888888889 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 484 KB Output isn't correct
3 Incorrect 3 ms 560 KB Output isn't correct
4 Incorrect 4 ms 736 KB Output isn't correct
5 Incorrect 3 ms 736 KB Output isn't correct
6 Incorrect 3 ms 736 KB Output isn't correct
7 Incorrect 3 ms 736 KB Output isn't correct
8 Incorrect 2 ms 736 KB Output isn't correct
9 Incorrect 3 ms 736 KB Output isn't correct
10 Correct 2 ms 736 KB Output is correct
11 Incorrect 2 ms 736 KB Output isn't correct
12 Incorrect 3 ms 744 KB Output isn't correct
13 Incorrect 2 ms 744 KB Output isn't correct
14 Incorrect 2 ms 748 KB Output isn't correct
15 Incorrect 3 ms 748 KB Output isn't correct
16 Incorrect 3 ms 748 KB Output isn't correct
17 Incorrect 3 ms 748 KB Output isn't correct
18 Incorrect 3 ms 748 KB Output isn't correct
19 Incorrect 2 ms 748 KB Output isn't correct
20 Incorrect 3 ms 748 KB Output isn't correct
21 Incorrect 4 ms 748 KB Output isn't correct
22 Incorrect 3 ms 748 KB Output isn't correct
23 Incorrect 4 ms 748 KB Output isn't correct
24 Incorrect 3 ms 752 KB Output isn't correct
25 Incorrect 3 ms 752 KB Output isn't correct
26 Incorrect 4 ms 752 KB Output isn't correct
27 Incorrect 3 ms 752 KB Output isn't correct
28 Incorrect 3 ms 752 KB Output isn't correct
29 Incorrect 3 ms 752 KB Output isn't correct
30 Incorrect 3 ms 752 KB Output isn't correct
31 Incorrect 3 ms 752 KB Output isn't correct
32 Incorrect 3 ms 752 KB Output isn't correct
33 Incorrect 3 ms 752 KB Output isn't correct
34 Incorrect 2 ms 752 KB Output isn't correct
35 Incorrect 3 ms 752 KB Output isn't correct
36 Incorrect 3 ms 752 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1388 KB Output isn't correct
2 Incorrect 6 ms 1772 KB Output isn't correct
3 Incorrect 5 ms 1772 KB Output isn't correct
4 Incorrect 5 ms 1772 KB Output isn't correct
5 Incorrect 9 ms 1772 KB Output isn't correct
6 Incorrect 7 ms 2156 KB Output isn't correct
7 Incorrect 6 ms 2156 KB Output isn't correct
8 Incorrect 6 ms 2156 KB Output isn't correct
9 Incorrect 6 ms 2156 KB Output isn't correct
10 Incorrect 6 ms 2156 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 20120 KB Output isn't correct
2 Incorrect 57 ms 20120 KB Output isn't correct
3 Incorrect 51 ms 20388 KB Output isn't correct
4 Incorrect 48 ms 20716 KB Output isn't correct
5 Incorrect 77 ms 23128 KB Output isn't correct
6 Incorrect 37 ms 23128 KB Output isn't correct
7 Incorrect 47 ms 23128 KB Output isn't correct
8 Incorrect 46 ms 23128 KB Output isn't correct
9 Incorrect 40 ms 23128 KB Output isn't correct
10 Incorrect 47 ms 23128 KB Output isn't correct
11 Incorrect 58 ms 23128 KB Output isn't correct
12 Incorrect 60 ms 23128 KB Output isn't correct
13 Incorrect 64 ms 23128 KB Output isn't correct
14 Incorrect 64 ms 23128 KB Output isn't correct
15 Incorrect 55 ms 23128 KB Output isn't correct
16 Incorrect 47 ms 23128 KB Output isn't correct
17 Incorrect 54 ms 23128 KB Output isn't correct
18 Incorrect 56 ms 23128 KB Output isn't correct
19 Incorrect 51 ms 23128 KB Output isn't correct
20 Incorrect 53 ms 23128 KB Output isn't correct