제출 #330102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330102		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(alteredHeights[i]);
        }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 i = 0; i < N; i++){
//         if(a[i] < 0){
//             continue;
//         }
//         int lo = upper_bound(bes.begin(), bes.end(), a[i]) - bes.begin(); 
//         if (lo == sz(bes)) bes.push_back(0);
//         bes[lo] = a[i];
//             // 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 - sz(bes) + 1 << '\n';
// }

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