제출 #676331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676331		Johann	Vim (BOI13_vim)	C++14	100 / 100	86 ms	55256 KiB

vim

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

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

const int A = 11; // number of characters + 1

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

    int n = 0, nin;
    cin >> nin;
    string s;
    cin >> s;

    // preperation
    vi text, underlined;
    int deleteWork = 0;
    bool underline;
    for (int i = 0; i < nin; ++i)
    {
        if (s[i] == 'e')
        {
            ++deleteWork;
            if (n > 0)
            { // not leading 'e's
                ++deleteWork;
                underline = true;
            }
        }
        else
        {
            text.push_back(s[i] - 'a');
            ++n;
            underlined.push_back(underline);
            underline = false;
        }
    }

    // DP
    vvi P(n + 1, vi(A, 1e9));
    vvvi Q(n + 1, vvi(A, vi(A, 1e9)));
    P[0][text[0]] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int c = 0; c < A; ++c)
        {
            // fill P
            int h = 1e9;
            if (c != text[i - 1] && !underlined[i - 1])
                h = min(h, P[i - 1][c]);
            h = min(h, P[i - 1][text[i - 1]] + 2);
            if (c != text[i - 1])
                h = min(h, Q[i - 1][text[i - 1]][c]);
            h = min(h, Q[i - 1][text[i - 1]][text[i - 1]] + 2);
            P[i][c] = h;
            // fill Q
            for (int d = 0; d < A; ++d)
            {
                h = 1e9;
                if (c != text[i - 1])
                    h = min(h, P[i - 1][c] + 3);
                h = min(h, P[i - 1][text[i - 1]] + 5);
                if (c != text[i - 1] && d != text[i - 1])
                    h = min(h, Q[i - 1][c][d] + 1);
                if (c != text[i - 1])
                    h = min(h, Q[i - 1][c][text[i - 1]] + 3);
                if (d != text[i - 1])
                    h = min(h, Q[i - 1][text[i - 1]][d] + 3);
                h = min(h, Q[i - 1][text[i - 1]][text[i - 1]] + 5);
                Q[i][c][d] = h;
            }
        }
    }
    cout << P[n][A - 1] + deleteWork - 2 << "\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

vim.cpp: In function 'int main()':
vim.cpp:40:34: warning: 'underline' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |             underlined.push_back(underline);
      |                                  ^~~~~~~~~

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