Submission #740862

#	Time	Username	Problem	Language	Result	Execution time	Memory
740862		old_school	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	36 ms	6980 KiB

triusis

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll            long long
#define ld            long double
#define pb            push_back
#define ppb           pop_back
#define F             first
#define S             second
#define nl            '\n'
#define YES           cout << "YES\n";
#define NO            cout << "NO\n";
#define all(c)        (c).begin(), (c).end()
#define sz(c)         (ll)(c).size()
#define MOD           (ll) 1e9 + 7 // 998244353
#define MAX           (ll) 1e5 + 5
#define INF           (ll) 1e18
#define itr(i, a, b)  for (ll i = a; i <= b; i++)
#define itrn(i, a, b) for (ll i = a; i >= b; i--)
#define iot(n)        for (ll i = 0; i < n; i++)
#define jot(n)        for (ll j = 0; j < n; j++)
#define pls(n, arr) \
    ll arr[n];  \
    iot(n) cin >> arr[i];

typedef pair<ll, ll> pii;

template <typename T> bool mycomp(T x, T y)
{
    return (x == y);
}

/******************************I/O******************************/
#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);

template <typename T> void input(T &&t)
{
    cin >> t;
}
template <typename T, typename... Args> void input(T &&t, Args &&...args)
{
    cin >> t;
    input(forward<Args>(args)...);
}

template <typename T> void print(T &&t)
{
    cout << t << " ";
}
template <typename T, typename... Args> void print(T &&t, Args &&...args)
{
    cout << t << " ";
    print(forward<Args>(args)...);
}
/******************************End******************************/
ll lis(vector<ll> &b)
{
    ll n = sz(b);
    vector<ll> d(n, INF);
    ll ans = 0;
    iot(n)
    {
        auto itr = upper_bound(all(d), b[i]);
        ll ind = itr - d.begin();
        d[ind] = b[i];
        ans = max(ans, ind + 1);
    }
    return ans;
}
void solve()
{
    ll n, m;
    input(n, m);
    pls(n, a);
    vector<ll> b;
    iot(n) if (m * (i + 1) >= a[i]) b.pb((m * (i + 1) - a[i]));
    print(n - lis(b));
}

int main()
{
    fast_io;
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << nl;
    }
}

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