Submission #1112862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112862		slycelote	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	592 KiB

triusis

#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

using ll = long long;

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

    int n, m; cin >> n >> m;
    const ll NEGINF = -1 - (n+1)*m;

    vector<ll> a(n+2);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] -= i*m;
    }
    a[n+1] = NEGINF;

    vector<int> dp(n+2);
    for (int i = n; i >= 0; --i) {
        int j = i+1;
        while (a[j] > a[i])
            ++j;
        dp[i] = dp[j] + j - i - 1;

        ll maxval = NEGINF;
        for (int j = i+1; j <= n+1; ++j) {
            if (maxval < a[j] && a[j] <= a[i]) {
                dp[i] = min(dp[i], dp[j] + j - i - 1);
            }
            maxval = max(maxval, a[j]);
        }

    }

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

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