제출 #44245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44245		neutron_byte	Vim (BOI13_vim)	C++17	4.17 / 100	2082 ms	1276 KiB

vim

#include <bits/stdc++.h>
#define INF 10000000
using namespace std;

int main() {
    int n; cin >> n;
    string s; cin >> s;

    int dp[n];
    dp[n - 1] = 0;

    for (int i = n - 2; i >= 0; --i) {
        if (s[i] == 'e') {
            dp[i] = 1 + dp[i + 1];
            continue;
        }

        dp[i] = INF;

        // check all possibilities to jump
        for (char c = 'a'; c <= 'j'; ++c) {
            if (c == 'e') continue;

            // find next occurrence
            int pos = i + 1;
            while (pos < n && s[pos] != c) {
                ++pos;
            }

            if (pos >= n) {
                continue;
            }

            // jump from i to pos

            int firstE = -1;
            int cntE = 0;

            for (int j = pos - 1; j > i; --j) {
                if (s[j] == 'e') {
                    ++cntE;
                    firstE = j;
                }
            }

            bool onlyE = true;
            for (int j = pos - 1; j >= firstE; --j) {
                if (s[j] != 'e') {
                    onlyE = false;
                    break;
                }
            }

            int afterE = 0;
            for (int j = pos + 1; j < n; ++j) {
                if (s[j] == 'e') ++afterE;
            }

            if (afterE > 0) {
                for (char d = 'a'; d <= 'j'; ++d) {
                    if (d == 'e') continue;
                    bool betweenE = false;
                    int nextOcc = -1;
                    for (int j = i + 1; j < n; ++j) {
                        if (s[j] == d) {
                            nextOcc = j;
                            break;
                        }
                    }

                    if (nextOcc == -1 || nextOcc < pos) continue;
                    for (int j = pos + 1; j <= nextOcc; ++j) {
                        if (s[j] == 'e') {
                            betweenE = true;
                            break;
                        }
                    }

                    if (!betweenE) {
                        if (cntE > 0) dp[i] = min(dp[i], (onlyE ? 2 : 4) + pos - firstE + cntE + dp[nextOcc]);
                        else dp[i] = min(dp[i], 2 + dp[nextOcc]);
                    }
                }

            } else {
                if (cntE > 0) dp[i] = min(dp[i], 2 + pos - firstE + cntE);
                else dp[i] = 0;
            }
        }

/*
            if (cntE > 0) {
                if (afterE > 0) {
                    dp[i] = min(dp[i], (onlyE ? 2 : 4) + pos - firstE + cntE + dp[pos]);
                } else {
                    dp[i] = min(dp[i], 2 + pos - firstE + cntE);
                }
            } else {
                if (afterE > 0) {
                    dp[i] = min(dp[i], 2 + dp[pos]);
                } else {
                    dp[i] = 0;
                }
            }
        }
*/
    }

/*
    for (int i = 0; i < n; ++i) {
        cout << "dp[" << i << "] = " << dp[i] << endl;
    }
*/

    cout << dp[0] << endl;
    return 0;
}

• Subtask 1: 4.166666666666667 / 50
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40