oj.uz

Submission #413724

# Submission time Handle Problem Language Result Execution time Memory
413724 2021-05-29T09:33:39 Z duyanh1704 Rabbit Carrot (LMIO19_triusis) C++14
0 / 100
 1 ms 204 KB 
#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e15 + 9;
int n, m, res;
long long a[1000005];

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        int x; cin >> x;
        a[i] = m * i - x;
    }

    vector<long long> f(n + 5, inf);
    f[0] = -inf;
    for (int i = 1; i <= n; ++i){
        int k = upper_bound(f.begin(), f.end(), a[i]) - f.begin();
        res = max(res, k);
        f[k] = a[i];
    }

    cout << n  - res << endl;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 37.0

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