제출 #483035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483035		keertan	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	27 ms	5304 KiB

triusis

/**
 * If you live in an imaginary world when your imaginary situation is encountered in 
 * real situation you can't enjoy it because you have to do pending work.
 * {This pending work appeared because you wasted that time on your useless
 * imaginary thinking.}
 */
#include<bits/stdc++.h>
using namespace std;
//#define int  int64_t
#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
#define sz(x) (int32_t)(x.size())
const int N=1e2;

void solve(){
    int n,m;
    cin>>n>>m;
    vector<int>z(n+1);
    for (int i=1;i<=n;i++){cin>>z[i];}
    vector<int> con;
    for (int i=1;i<=n;i++){
        if (i*m>=z[i]){
            con.push_back(i*m-z[i]);
        }
    }
    vector<int> dp;
    for (int &it:con){
        int pos=upper_bound(all(dp),it)-dp.begin();
        if (pos==sz(dp)){
            dp.push_back(it);
        }
        else{
            dp[pos]=it;
        }
    }
    cout<<n-sz(dp);
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tq=1;
    //cin>>tq;
    for (;tq;tq--){solve();}
}
//is a brute-force possible?
//think greedier, make more assumptions
// if you find a solution using a loop to decrease complexity use bs
//stuck for more than 5 minutes? move on 

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