Submission #629644

#	Time	Username	Problem	Language	Result	Execution time	Memory
629644		finn__	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	300 KiB

triusis

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

int main()
{
    size_t n;
    int m;
    cin >> n >> m;

    vector<int> h(n);
    for (size_t i = 0; i < n; i++)
        cin >> h[i];

    vector<unsigned> dp1(n, UINT_MAX);
    vector<unsigned> dp2(n, UINT_MAX);

    if (h[0] > m)
    {
        dp2[0] = 1;
        h[0] = m;
    }
    else
    {
        dp1[0] = 0;
        dp2[0] = 0;
    }

    vector<int> h1 = h;
    vector<int> h2 = h;

    for (size_t i = 0; i < n - 1; i++)
    {
        if (h1[i + 1] - h1[i] <= m)
        {
            dp1[i + 1] = min(dp1[i], dp2[i]);
        }
        else if (h1[i + 1] - h1[i - 1] <= 2 * m)
        {
            dp1[i + 1] = dp1[i] + 1;
            h1[i] = h[i + 1] - m;
        }
        else
        {
            h1[i + 1] = h2[i] + m;
        }

        if (h2[i + 1] - h2[i] <= m)
        {
            dp2[i + 1] = min(dp1[i], dp2[i]);
        }
        else
        {
            dp2[i + 1] = min(dp1[i], dp2[i]) + 1;
            h2[i + 1] = h2[i] + m;
        }
    }

    cout << min(dp1[n - 1], dp2[n - 1]) << '\n';
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37