Submission #63294

#	Time	Username	Problem	Language	Result	Execution time	Memory
63294		imeimi2000	Vim (BOI13_vim)	C++17	100 / 100	89 ms	23164 KiB

vim

#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;
        }
    }
    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 = 0; i < n; ++i) {
        for (int j = 0; j < 10; ++j) {
            dp1[i + 1][j] = inf;
            if (j != str[i] && !ch[i]) setMin(dp1[i + 1][j], dp1[i][j]);
            if (j != str[i]) setMin(dp1[i + 1][j], dp2[i][str[i]][j]);
            setMin(dp1[i + 1][j], dp1[i][str[i]] + 2);
            setMin(dp1[i + 1][j], dp2[i][str[i]][str[i]] + 2);
            
            for (int k = 0; k < 10; ++k) {
                dp2[i + 1][j][k] = inf;
                setMin(dp2[i + 1][j][k], dp1[i][str[i]] + 5);
                setMin(dp2[i + 1][j][k], dp2[i][str[i]][str[i]] + 5);
                if (j != str[i]) {
                    setMin(dp2[i + 1][j][k], dp1[i][j] + 3);
                    setMin(dp2[i + 1][j][k], dp2[i][j][str[i]] + 3);
                }
                if (k != str[i]) {
                    setMin(dp2[i + 1][j][k], dp2[i][str[i]][k] + 3);
                }
                if (j != str[i] && k != str[i])
                    setMin(dp2[i + 1][j][k], dp2[i][j][k] + 1);
            }
        }
    }
    printf("%d\n", dp1[n][9] + er - 2);
	return 0;
}

Compilation message (stderr)

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: 50 / 50
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40