Submission #330100

#	Time	Username	Problem	Language	Result	Execution time	Memory
330100		alien_lover	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	30 ms	4072 KiB

triusis

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

typedef long long ll;

#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()

const int PRIME = 1e9 + 7;


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

//     int n;
//     ll m;
//     cin >> n >> m;
    
//     vector<ll> alteredHeights(n);

//     for(int i = 0; i < n; i++){
//         ll h;
//         cin >> h;
//         alteredHeights[i] = m * (ll)(i+1) - h;
//     }

//     vector<ll> dp;
//     dp.push_back(LLONG_MIN);

//     for(int i = 0; i < n; i++){
//         if(alteredHeights[i] < 0){
//             continue;
//         }
//         int ind = upper_bound(dp.begin(), dp.end(), alteredHeights[i]) - dp.begin();
//         if(ind == sz(dp)){
//             dp.push_back(0);
//         }else{
//             dp[ind] = alteredHeights[i];
//         }
//     }

//     cout << n - dp.size() + 1 << '\n';
// }


// void add(ll x) {
//     int lo = upper_bound(all(bes), x) - begin(bes); 
//     if (lo == sz(bes)) bes.push_back(0);
//     bes[lo] = x;
// }

int N;
ll M;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    vector<ll> a(N);
    for(int i = 0; i < N; i++){
        ll h;
        cin >> h;
        a[i] = M * (i+1) - h;
    }
    vector<ll> bes;
    bes.push_back(LLONG_MIN);

    // for(int i = 0; i < N; i++){
    //     a[i] = M * (i+1) - a[i];
    // }
    for(int el: a){
        if(el < 0){
            continue;
        }
        int lo = upper_bound(all(bes), el) - begin(bes); 
        if (lo == sz(bes)) bes.push_back(0);
        bes[lo] = el;
    }
    cout << N - sz(bes) + 1 << '\n';
}

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