Submission #991698

#	Time	Username	Problem	Language	Result	Execution time	Memory
991698		SnowRaven52	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	56 ms	5400 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

int main() {
    // freopen("main.in", "r", stdin);
    // freopen(".out", "w", stdout);

    int n, h; cin >> n >> h;
    vector<int> poles(n);
    for (int i = 0; i < n; i++) cin >> poles[i];
    vector<int> same;
    for(int i = 1; i <= n; i++)
        if(i * h >= poles[i-1]) same.push_back(i * h - poles[i - 1]);
    
    vector<int> min_endings;
    for (auto i : same){
        int pos = upper_bound(min_endings.begin(), min_endings.end(), i) - min_endings.begin();
        if(pos == int(min_endings.size())) min_endings.push_back(i);
        else min_endings[pos] = i;
    }
    cout << n - int(min_endings.size()) << endl;
}

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