Submission #797085

#	Time	Username	Problem	Language	Result	Execution time	Memory
797085		KindaNameless	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	24 ms	2516 KiB

triusis

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

#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()

vector<int> dp;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N; ll M; cin >> N >> M;

    for(int i = 1; i <= N; ++i){
        ll h; cin >> h;
        if(M * (ll)i - h >= 0){
            ll val = M * (ll)i - h;
            auto pos = upper_bound(dp.begin(), dp.end(), val);
            if(pos == dp.end()){
                dp.push_back(val);
            }
            else{
                dp[pos - dp.begin()] = val;
            }
        }
    }

    cout << N - (int)dp.size();

    return 0;
}

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