Submission #882069

#	Time	Username	Problem	Language	Result	Execution time	Memory
882069		skywwla	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	600 KiB

triusis

#include <bits/stdc++.h>

using namespace std ;
using ll = long long ;

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    int n , m ; cin >> n >> m ;
    vector<ll> a(n) ;
    for (ll &i : a) cin >> i ;
    vector<ll> b ;
    for (int i = 0 ; i < n ; i++) {
        ll cur = (i + 1) * m - a[i] ;
        if (cur >= 0) {
            b.push_back(cur) ;
        }
    }
    auto calc = [&](vector<ll>& v) -> int {
        multiset<pair<ll,ll>> s;
        for (ll i : v) {
            if (!s.size()) {
                s.insert({i, 1}) ;
                continue ;
            }
            auto it = s.upper_bound({i, i}) ;
            if (it == s.begin()) {
                s.insert({i, 1}) ;
            } else { it-- ;
                auto [value, dp] = *it ;
                s.erase(it) ;
                s.insert({i, dp + 1}) ;
            }
        }
        ll mx = 0 ;
        for (auto [v, dp] : s) {
            mx = max(mx ,dp) ;
        }
        return mx ;
    };
//    cout << calc(b) << "\n" ;
    cout << n - calc(b) ;
    return 0 ;
}

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