제출 #1206580

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206580		mopsyarka	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	55 ms	3688 KiB

triusis

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define f first
#define s second

#define sz(x) (ll)(x.size())

#define vec vector
#define pb push_back
#define all(x) x.begin(), x.end()

#define debug(x) cerr << (#x) << " = " << (x) << endl

ll pw (int a) {
    return 1ll << a;
}

using pii = pair < int, int >;
using pll = pair < ll, ll >;

const int mod = 998244353;
const int N = 2e5 + 5;
const ll OO = 1e18;
const ld eps = 1e-10;

template<typename T>
bool umn (T &fi, T se) { return fi > se ? (fi = se, 1) : 0; }

template<typename T>
bool umx (T &fi, T se) { return fi < se ? (fi = se, 1) : 0; }

int a[N], dp[N];

int bit[N];

void update (int i, int x) {
    for (; i < N; i |= i + 1)
        umn(bit[i], x);
}

int get (int i) {
    int ans = N;
    for (; i >= 0; i = (i & (i + 1)) - 1)
        umn(ans, bit[i]);
    return ans;
}

void slv () {
//    freopen("cowjog.in", "r", stdin);
//    freopen("cowjog.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    a[0] = 0;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    a[n + 1] = 0;
    dp[n + 1] = 0;

    vec < int > c;
    for (int i = 0; i <= n + 1; ++i) {
        c.push_back(a[i] - m * i);
    }
    sort(all(c));
    c.erase(unique(all(c)), c.end());
    for (int i = 0; i < N; ++i)
        bit[i] = N;
    update(0, n + 1);

    for (int i = n; i >= 0; --i) {
        dp[i] = n;
        int v = a[i] - m * i;
        int pp = lower_bound(all(c), v) - c.begin();
        dp[i] = get(pp) - i - 1;
        update(pp, dp[i] + i);

//        for (int j = i + 1; j <= n + 1; ++j) {
//            if (a[i] - m * i >= a[j] - m * j)
//                dp[i] = min(dp[i], dp[j] + j - i - 1);
//        }
    }
    cout << dp[0];
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
//    cin >> test;
    while (test--) {
        slv();
        cout << "\n";
    }
}

///    Skyline Ryodan

///Да это же Midix!
///Trippy, cooking that shit up again

///Мой quinque это Desolator, да, я Сузуя Джузо
///Видел так много смертей близких, затупились все чувства
///Читаю словно на спидах, бля, я Ликаном покусан
///Какой паук тебе, пацан? Ты — человеческий мусор
///Я ебанутый на голову, скорость ударила в голову
///Будешь пиздеть — с корнями вырву твою голову
///В моей системе веет од, паук не знает слова «голод»
///Оставлю пару пулевых на теле, сука, мне не нужен повод

///Это Редан, здесь пауки, в Sky'е летим прямо в ад
///Если ты прыгнул в этот сквад, то точно нет пути назад
///Да твои парни — это крысы, будто Хилл Зодиак
///И моя клика вырубает вас за пару атак!

///Юзаю drug, я перебил стак, ты знаешь как мне похуй на luck
///На линзах мрак, нет, это не знак, я знаю: ты слаб, ты ёбаный раб
///Продал души, я бессмертен, кровью подписан контракт
///И под звуки Реквиема я танцую на костях!

///Всё, что держу в своих руках — это я сделал сам
///Я не нуждаюсь в представлении, Jinada скам
///Здесь пауки, мы поколение, со мной Редан
///Skyline узнает где ты, сука, нам не нужен скан (Ра)
///Пауков целая стая, психопаты за рулём
///За штурвал hikikomori, левый глаз залит огнём
///Весь салон пропитан болью и я роллю прямо в нём
///И под капотом триста двадцать, насладись последним днём, а

///Это mindset от Бога
///Моё дыхание грома
///Мои глаза видят пустых — это глаукома
///Это mindset от Бога-Бога
///Моё дыхание грома
///Мои гла—, мои гла— видят пустых, глаук—

///Проклятый ублюдок, на мне метка паука
///Двенадцать лап на моей шее, подо мной крови река
///Полный бак залитый в Sky'е, по мне плачут небеса
///Клеймо четвёрки на спине и труппа, скрытая в тенях

///Я ебанутый на голову, скорость ударила в голову
///Будешь пиздеть — с корнями вырву твою голову
///Я ебанутый на голову, скорость ударила в голову
///Будешь пиздеть — с корнями вырву твою голову
///Аллё, shadow-shadow, блядь, сук—, идите нахуй
///Отпустите меня домой, ха-ха-ха

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