Submission #893849

#	Time	Username	Problem	Language	Result	Execution time	Memory
893849		agawron	Rabbit Carrot (LMIO19_triusis)	C++14	0 / 100	0 ms	348 KiB

triusis

#include<bits/stdc++.h>

using namespace std;

#define pb push_back


constexpr int MAX_N = 2e5 + 5;
constexpr int INF = 1e9;

int n, m;
int a[MAX_N];
int b[MAX_N];

vector <int> v;

int LIS(){
    int sz = v.size();

    vector <int> d(sz + 1, INF);
    d[0] = -INF;


    for(int i = 0; i < sz; i++){
        int l = upper_bound(d.begin(), d.end(), v[i]) - d.begin();
        if(d[l - 1] <= v[i] && v[i] < d[l]){
            d[l] = a[i];
        }
    }

    int ans = 0;

    for(int i = 0; i <= sz; i++){
        if(d[i] < INF){
            ans = i;
        }
    }

    return ans;
}


int main(){
    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }

    int cnt = 0;

    for(int i = 1; i <= n; i++){
        b[i] = m * i - a[i];

        if(b[i] >= 0) v.pb(b[i]);
    }

    cnt = n - LIS();

    printf("%d\n", cnt);
    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
triusis.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

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