Submission #674452

#	Time	Username	Problem	Language	Result	Execution time	Memory
674452		Johann	Vim (BOI13_vim)	C++14	39.50 / 100	32 ms	10568 KiB

vim

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(), (x).end()

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    string s;
    cin >> s;

    // Init Jumpings
    vvi next_loc(n, vi(10, n));
    int cntE = 0; // der letzte und erste Buchstabe sind != 'e'
    for (int i = n - 2; i >= 0; --i)
    {
        for (int c = 0; c < 10; ++c)
            next_loc[i][c] = next_loc[i + 1][c];
        next_loc[i][s[i + 1] - 'a'] = i + 1;
        if (s[i + 1] == 'e')
            ++cntE;
    }

    // make dp
    vvi dp(n, vi(10, INT_MAX));
    vi dpmin(n + 1, INT_MAX);
    dpmin[n] = 0;
    for (int i = n - 1, l; i >= 0; --i)
    {
        l = next_loc[i]['e' - 'a']; // idx of next 'e'
        for (int c = 0, k; c < 10; ++c)
        {
            k = next_loc[i][c]; // jmp location
            if (l == n)         // es gibt kein 'e'
                dp[i][c] = 0;
            if (c == 'e' - 'a' || k == n || l == n) // in diesen Faellen darf oder gibt es nichts zu tun
                continue;
            if (l > k)
                dp[i][c] = 2 + dpmin[k];
            else
            {
                if (dpmin[k] == 0)
                    dp[i][c] = 0;
                else
                    dp[i][c] = 2 + dpmin[k];    // sichere Moeglichkeit: Sprung zu c, dann weiter
                for (int c2 = 0; c2 < 10; ++c2) // potentiell besser: sprung direkt ueber c hinaus zu c2
                    if (next_loc[l + 1][c2] < n && next_loc[l + 1][c2] > k)
                        dp[i][c] = min(dp[i][c], dp[k][c2]);
                dp[i][c] += 2 + (k - l); // arbeit um das erste e zu kommen (eigentlich der erste Schritt)
            }
        }

        dpmin[i] = *min_element(all(dp[i]));
    }
    cout << dpmin[0] + cntE << endl;
    return 0;
}

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