Submission #1241747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241747		datluong_04	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	1 ms	328 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define maxn 200005
#define FOR(i , a , b) for(int i = a ; i <= b; i++)
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int a[maxn];
ll b[maxn] ,c[maxn];

int main(){
    FAST;
    int n;
    ll M;
    cin >> n >> M;
    FOR(i , 1 , n) cin >> a[i];
    vector<ll> c;
    FOR(i , 1 , n) if(M * i >= a[i]) c.push_back(M * i - a[i]);
    if(c.empty()){
        cout << n;
        return 0;
    }
    
    int len = c.size();
    FOR(i , 0 , len - 1) b[i] = 2e18;

    int ans = 0;

    FOR(i , 0 , len - 1){
        int k = upper_bound(b, b + n , c[i]) - b;
        b[k] = c[i];
        ans = max(ans , k + 1);
    }

    cout << n - ans;
}

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