Submission #1241751

#TimeUsernameProblemLanguageResultExecution timeMemory
1241751datluong_04Rabbit Carrot (LMIO19_triusis)C++20
100 / 100
20 ms4168 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define maxn 200005 #define FOR(i , a , b) for(int i = a ; i <= b; i++) #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a[maxn]; ll b[maxn] ,c[maxn]; int main(){ FAST; int n; ll M; cin >> n >> M; FOR(i , 1 , n) cin >> a[i]; int c_pos = 0; FOR(i , 1 , n){ if(M * i >= a[i]){ c[++c_pos] = M * i - 1ll*a[i]; } } FOR(i , 1 , c_pos) b[i] = 2e9; int ans = 0; FOR(i , 1 , c_pos){ int k = upper_bound(b + 1, b + c_pos + 1, c[i]) - b; b[k] = c[i]; ans = max(ans , k); } cout << n - ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...