oj.uz

Submission #740851

# Submission time Handle Problem Language Result Execution time Memory
740851 2023-05-13T07:47:39 Z old_school Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1 ms 212 KB 
#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 + 1];  \
    iot(n) cin >> arr[i + 1];

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(ll b[], ll n)
{
    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);
    ll b[n];
    iot(n) b[i] = m * (i + 1) - a[i];
    print(n - lis(b, n));
}

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 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 212 KB Output is correct
2 Incorrect 1 ms 212 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 212 KB Output is correct
2 Incorrect 1 ms 212 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 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -