Submission #1183577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183577		mir4ge	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	16 ms	3520 KiB

triusis

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define MULTI 0
#define all(x) (x).begin(), (x).end()
#define dbg(x) cout << #x << " = " << x << "\n"
#define cin_vector(vec, n, T) vector<T> vec(n); for(ll i = 0; i < n; i++) cin >> vec[i];

template <typename ll> void print(vector<ll> &v){ for (auto &a : v) cout << a << " "; cout << "\n";}
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve() {
    int n, base;
    cin>>n>>base;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    vector<int> poss_unch;
    vector<int> b;
    for(int i=1; i<=n; i++){
        if(i*base>=a[i-1]){
            b.push_back(i*base-a[i-1]);
        }
    }
    // print(b);
    vector<int> s;
    for(auto p: b){
        int pos = upper_bound(all(s),p) - s.begin();
        if(pos==s.size()) s.push_back(p);
        else s[pos]=p;
    }

    cout<<n-s.size()<<endl;

}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout.precision(15); cout.setf(ios::fixed);
    ll t=1; if(MULTI) cin>>t;
    for (ll it = 1; it <= t; it++) {
        // cout << "Case #" << it << ": ";
        solve();
    }
    return 0;
}

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