Submission #648455

#	Time	Username	Problem	Language	Result	Execution time	Memory
648455		borisAngelov	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	37 ms	4732 KiB

triusis

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
const int INF = 2000000000;

int n, m;
int a[MAXN];

vector<int> b;

int min_end[MAXN];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (m * i - a[i] >= 0) b.push_back(m * i - a[i]);
    }

    min_end[0] = -INF;
    for (int i = 1; i <= n; i++) min_end[i] = INF;

    int ans = 0;

    for (int i = 0; i < b.size(); i++) {
        int idx = upper_bound(min_end + 1, min_end + n + 1, b[i]) - min_end;
        idx--;

        ans = max(ans, idx + 1);
        min_end[idx + 1] = min(min_end[idx + 1], b[i]);
    }

    cout << n - ans << endl;

    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < b.size(); i++) {
      |                     ~~^~~~~~~~~~

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