Submission #947239

#	Time	Username	Problem	Language	Result	Execution time	Memory
947239		VMaksimoski008	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	139 ms	14856 KiB

triusis

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

int tree[200500], n, h, v[200500], dp[200500];

void update(int p, int v) {
    for(p++; p<200500; p+=p&-p) tree[p] = max(tree[p], v);
}

int query(int p) {
    int ans = 0;
    for(p++; p>0; p-=p&-p) ans = max(ans, tree[p]);
    return ans;
}

int main() {
    cin >> n >> h;

    set<int> s;
    for(int i=1; i<=n; i++) cin >> v[i], v[i] = 1ll * h * i - v[i];
    for(int i=0; i<=n; i++) s.insert(v[i]);
    vector<int> comp(s.begin(), s.end());

    for(int i=1; i<=n; i++) {
        int p = lower_bound(comp.begin(), comp.end(), v[i]) - comp.begin();
        if(v[i] >= 0) dp[i] = query(p) + 1;
        if(v[i] >= 0) update(p, dp[i]);
    }

    cout << n - query(n+5) << '\n';
    return 0;
}

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