Submission #1128896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128896		Yang8on	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	77 ms	3436 KiB

triusis

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const long long MAXN = 2e5+5;
long long arr[MAXN];
long long d[MAXN];
int main(){
    long long n,k;
    cin>>n>>k;
    const long long INF = 1e18;
    vector<long long> d(n+2, -INF);
    d[n+1] = 0;
    
    for(long long i=1;i<=n;i++){
        cin>>arr[i];
        arr[i]-=(k*i);
        
    }
    for(long long i=1;i<=n;i++){
        long long j = lower_bound(d.begin(), d.end(), arr[i]) - d.begin();
        
        if(j<=(n+1) && d[j-1]<=arr[i] && d[j]>=arr[i]){
            d[j-1] = arr[i];
        }
       // cout<<arr[i]<<" "<<j<<endl;
    }
    long long ans = 0;
    
    for(long long i=1;i<=n;i++){
        if(d[i]!=-1e18){
           ans = max(ans,n-i+1);
        }
    }
    cout<<n-ans<<endl;
    return 0;
}

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