Submission #1112863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112863		slycelote	Rabbit Carrot (LMIO19_triusis)	C++17	63 / 100	1051 ms	3256 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) {
        dp[i] = n;
        for (int j = i+1; j <= n+1; ++j) if (a[j] <= a[i]) {
            dp[i] = min(dp[i], dp[j] + j - i - 1);
        }
    }

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

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