Submission #570556

#	Time	Username	Problem	Language	Result	Execution time	Memory
570556		duydong05	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	34 ms	8436 KiB

triusis

#include <bits/stdc++.h>
#define ll long long 
#define pii pair <int , int >
#define pll pair <ll, ll >
#define FOR(i,a,b) for (int i = a; i <= b ; i++) 
#define FORD(i,a,b) for (int i =a;i >= b ; i--)
using namespace std;
const ll nMax= 2e5 +5;
const ll oo =1e9;
const ll mod =1e9 +7;
ll n, m , a[nMax] ,b[nMax],f[nMax], c[nMax];
ll sz = 0;
int lis() {
    int ret = 0;
    FOR(i,1,sz) {
        f[i] = upper_bound(c +1  , c +ret +1, b[i]) -c;
        ret= max(ret*1ll, f[i]);
        c[f[i]] = b[i];
    }
    return ret;

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m ;
    FOR(i,1,n ) cin >> a[i];
    FOR(i,1,n ) {
        if (m*i - a[i] >= 0) {
            b[++sz] = m*i - a[i];
        }
    }
    cout << n - lis();

}

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