Submission #839409

#TimeUsernameProblemLanguageResultExecution timeMemory
839409MathandskiRabbit Carrot (LMIO19_triusis)C++17
0 / 100
1 ms300 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define is insert #define ll long long #define V vector #define MS multiset #define PL pair<ll, ll> #define F first #define S second #define PQ priority_queue #define f0r(i, begin, end) for (ll i = begin; i < end; i ++) #define For(i, end, begin) for (ll i = end; i > begin; i --) #define all(x) x.begin(), x.end() #define INF 1000000000000000000 #define inf 1000000000 #define MOD 998244353 #define len(x) (ll)x.size() #define fileread(file) ifstream fin; fin.open((string)file + ".in"); ofstream fout; fout.open((string)file + ".out") #define fastio ios_base::sync_with_stdio(0LL); cin.tie(nullptr) template<typename T> istream& operator>>(istream& in, V<T>& a) {for(auto &x : a) in >> x; return in;}; template<typename T> ostream& operator<<(ostream& out, V<T>& a) {for(auto &x : a) out << x << ' '; return out;}; ll N, M; V<ll> heights; int main () { cin >> N >> M; f0r (i, 1, N + 1) { ll a; cin >> a; heights.pb(-a + i * M); } V<ll> dp; f0r (i, 0, N) { ll num = heights[i]; if (num < 0) continue; else if (dp.empty()) dp.pb(num); else if (num >= dp[len(dp) - 1]) dp.pb(num); else { ll pos = lower_bound(all(dp), num) - dp.begin(); dp[pos] = num; } } cout << N - len(dp) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...