Submission #1112864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112864		slycelote	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	21 ms	3152 KiB

triusis

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

using namespace std;

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

    int n, m; cin >> n >> m;

    const int NEGINF = -1 - n*m;
    vector<int> dp(n+2, NEGINF);
    dp[0] = 1000'000'010;
    dp[1] = 0;

    for (int i = 1; i <= n; ++i) {
        int a; cin >> a;
        a -= i*m;
        if (a <= 0) {
            auto it = upper_bound(dp.begin(), dp.end(), a, greater<>{});
            if (it != dp.end())
                *it = a;
        }
    }

    for (int i = n+1; i >= 0; --i) if (dp[i] > NEGINF) {
        cout << n+1-i << endl;
        break;
    }
}

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