Submission #516247

#	Time	Username	Problem	Language	Result	Execution time	Memory
516247		danikoynov	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	96 ms	3660 KiB

triusis

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxn = 2e5 + 10;
int n, m, a[maxn], dp[maxn];
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        a[i] = i * m - a[i];
    }

    int to = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (a[i] < 0)
            continue;
        int l = 0, r = to;
        while(l <= r)
        {
            int mid = (l + r) / 2;
            if (dp[mid] <= a[i])
                l = mid + 1;
            else
                r = mid - 1;
        }

        dp[l] = a[i];
        if (l > to)
            to = l;
    }

    cout << n - to << endl;

}

int main()
{
    solve();
    return 0;
}

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