Submission #1310991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310991		vaderspader	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	20 ms	4180 KiB

triusis

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> matrix;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define down(i, b, a) for(ll i = b - 1; i >= a; i--)

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, m;
    cin >> n >> m;

    vi p(n);
    rep(i, 0, n) cin >> p[i];

    rep(i, 0, n){
        p[i] = m * (i + 1) - p[i];
    }

    vi dp(0);

    rep(i, 0, n){
        if(p[i] < 0) continue;

        ll best = dp.size();

        ll l = 0, r = dp.size() - 1;

        while(l <= r){
            ll m = (l + r) / 2;

            if(dp[m] > p[i]){
                best = m;
                r = m - 1;
            }
            else l = m + 1;
        }

        if(best == dp.size()) dp.push_back(p[i]);
        else{
            dp[best] = p[i];
        }
    }

    cout << n - dp.size() << endl;
}

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