Submission #893855

#	Time	Username	Problem	Language	Result	Execution time	Memory
893855		agawron	Rabbit Carrot (LMIO19_triusis)	C++14	63 / 100	33 ms	5620 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] = v[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:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
triusis.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

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