Submission #1307464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307464		Owstin	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	18 ms	2628 KiB

triusis

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define umap unordered_map
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n; ll m; cin >> n >> m;
    vector<ll> dp;
    for (int i = 1; i <= n; i++) {
        ll x; cin >> x;
        if (x <= m * i) {
            auto it = upper_bound(all(dp), -x + m * i);
            if (it == dp.end()) {
                dp.pb(-x + m * i);
            }
            else {
                *it = -x + m * i;
            }
        }
    }
    cout << n - dp.size();
}

int main() {
    FAST_IO;
    //freopen("pcb.in", "r", stdin);
    //freopen("pcbout", "w", stdout);
    //TEST_CASES;
    solve(); cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}

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