답안 #674452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
674452 2022-12-24T10:05:59 Z Johann Vim (BOI13_vim) C++14
39.5 / 100
32 ms 10568 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 316 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Incorrect 0 ms 340 KB Output isn't correct
15 Incorrect 1 ms 316 KB Output isn't correct
16 Incorrect 0 ms 340 KB Output isn't correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 320 KB Output is correct
19 Incorrect 1 ms 340 KB Output isn't correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 324 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 320 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Incorrect 1 ms 340 KB Output isn't correct
30 Incorrect 0 ms 340 KB Output isn't correct
31 Correct 1 ms 316 KB Output is correct
32 Incorrect 1 ms 340 KB Output isn't correct
33 Correct 1 ms 324 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 320 KB Output is correct
36 Correct 1 ms 320 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 960 KB Output isn't correct
2 Correct 3 ms 980 KB Output is correct
3 Incorrect 2 ms 700 KB Output isn't correct
4 Incorrect 3 ms 980 KB Output isn't correct
5 Incorrect 2 ms 980 KB Output isn't correct
6 Incorrect 2 ms 968 KB Output isn't correct
7 Incorrect 2 ms 960 KB Output isn't correct
8 Incorrect 3 ms 980 KB Output isn't correct
9 Correct 3 ms 960 KB Output is correct
10 Incorrect 2 ms 980 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 9172 KB Output isn't correct
2 Incorrect 19 ms 8916 KB Output isn't correct
3 Incorrect 21 ms 9172 KB Output isn't correct
4 Incorrect 21 ms 10568 KB Output isn't correct
5 Incorrect 24 ms 10512 KB Output isn't correct
6 Incorrect 30 ms 9340 KB Output isn't correct
7 Incorrect 25 ms 9680 KB Output isn't correct
8 Incorrect 22 ms 9812 KB Output isn't correct
9 Incorrect 25 ms 9684 KB Output isn't correct
10 Incorrect 26 ms 9812 KB Output isn't correct
11 Incorrect 21 ms 10508 KB Output isn't correct
12 Incorrect 24 ms 10452 KB Output isn't correct
13 Incorrect 25 ms 10276 KB Output isn't correct
14 Incorrect 24 ms 10300 KB Output isn't correct
15 Incorrect 32 ms 10452 KB Output isn't correct
16 Incorrect 16 ms 9044 KB Output isn't correct
17 Incorrect 21 ms 9208 KB Output isn't correct
18 Incorrect 21 ms 9212 KB Output isn't correct
19 Incorrect 23 ms 9040 KB Output isn't correct
20 Incorrect 26 ms 9112 KB Output isn't correct