Submission #821219

#	Time	Username	Problem	Language	Result	Execution time	Memory
821219		rinho	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	26 ms	3932 KiB

triusis

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

const int Nmax = 2e5;
const int MOD = 1000000007;

int n, m, dp[Nmax + 3];
vector<int> b;

void in(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        int y = m * i - x;
        if(y >= 0) b.push_back(y);
    }
}
void sol(){
    memset(dp, 0x3f, sizeof dp);
    int ans = 0;
    for(auto i : b){
        int k = upper_bound(dp + 1, dp + n + 1, i) - (dp);
        ans = max(ans, k);
        dp[k] = i;
    }
    cout << n - ans;
}
int main(){
    //freopen(" ", "r", stdin);
    //freopen(" ", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
       in();
       sol();
    }
    return 0;
}

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