Submission #1084080

#TimeUsernameProblemLanguageResultExecution timeMemory
1084080vjudge1Rabbit Carrot (LMIO19_triusis)C++14
100 / 100
23 ms3164 KiB
#include <bits/stdc++.h> #define ll long long const ll I = 2e5 + 9; using namespace std; int tf = 0, n, M, dpm[I]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> M; dpm[1] = 0; tf = 1; for (int i = 1; i <= n; i++) { int x; cin >> x; if (x > i * M) continue; x = x - i * M; if (x <= dpm[tf]) { tf++; dpm[tf] = x; } else { int l_ = 1, r_ = tf, sav = 0, tg; while (l_ <= r_) { tg = (l_ + r_) / 2; if (dpm[tg] >= x) { sav = tg; l_ = tg + 1; } else r_ = tg - 1; } dpm[sav + 1] = max(dpm[sav + 1], x); } } cout << n - tf + 1; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...