Submission #1140210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140210		liangjeremy	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	31 ms	6588 KiB

triusis

#include<bits/stdc++.h>
#include<random>
using namespace std;
using db=double;
using ll=long long;
using sll=__int128;//super long long
using lb=long double;//lb is slow
//numbers for hashing: b(19260817),mod(998244353)
// freopen("lasers.in", "r", stdin);
// freopen("lasers.out", "w", stdout); 

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n,m; cin>>n>>m; vector<ll>a(n);
    for(ll i=0; i<n; i++){
        cin>>a[i];
    }
    vector<ll>v; vector<ll>dp;
    for(ll i=0; i<n; i++){
        if((i+1)*m-a[i]>=0){
            v.push_back((i+1)*m-a[i]);
        }
    }
    for(auto x:v){
        ll pos=upper_bound(dp.begin(),dp.end(),x)-dp.begin();
        if(pos==dp.size())dp.push_back(x);
        else dp[pos]=x;
    }
    ll ans=n-dp.size(); cout<<ans<<'\n';
}

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