Submission #1226626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226626		opeleklanos	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	56 ms	4028 KiB

triusis

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define ll long long

int main(void){
    //freopen("input.txt", "r", stdin);
    ll n, k;
    cin>>n>>k;

    vector<ll> arr(n, 0);

    for(ll i = 0; i<n; i++){
        ll a; cin>>a;
        arr[i] = a - (k*(i+1));
    }

    reverse(arr.begin(), arr.end());

    vector<ll> lis;
    for(ll i = 0; i<n; i++){
        auto ub = upper_bound(lis.begin(), lis.end(), arr[i]);
        if(ub == lis.end()) lis.push_back(arr[i]);
        else lis[ub - lis.begin()] = arr[i];
    }
    ll z = (upper_bound(lis.begin(), lis.end(), 0) - lis.begin());
    cout<<lis.size() - z + n - lis.size()<<endl;
}

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