oj.uz

Submission #893849

# Submission time Handle Problem Language Result Execution time Memory
893849 2023-12-27T14:39:24 Z agawron Rabbit Carrot (LMIO19_triusis) C++14
0 / 100
 0 ms 348 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -