Submission #333302

#	Time	Username	Problem	Language	Result	Execution time	Memory
333302		AmineTrabelsi	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	33 ms	4204 KiB

triusis

#include "bits/stdc++.h"
using namespace std;
// Hi ☻
vector<int> dp = {int(-(1e9+7))};
void add(int x){
    int pos = upper_bound(dp.begin(),dp.end(),x) - dp.begin();
    if(pos == (int)dp.size())dp.push_back(0);
    dp[pos] = x;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<int> v(n);
    for(auto &i:v)cin>>i;
    for(int i=0;i<n;i++){
        v[i] = m*(i+1) - v[i];
    }
    for(auto i:v){
        if(i >= 0)add(i);
    }
    cout<<n-dp.size()+1<<'\n';
    return 0;
}

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