Submission #1263864

#TimeUsernameProblemLanguageResultExecution timeMemory
1263864satyanshuRabbit Carrot (LMIO19_triusis)C++20
100 / 100
33 ms5144 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 998244353; const ll INF = 1e18 + 7; const int maxN = 1e6 + 7; void solve() { ll n, m; cin>>n>>m; vector<ll>a(n); vector<ll>b; for(int i=0;i<n;i++){ cin>>a[i]; ll temp = m*(i+1)-a[i]; if(temp >= 0){ b.push_back(temp); } } vector<ll>dp(n+1, INF); dp[0] = -INF; int ans = 0; for(auto it: b){ int ind = upper_bound(dp.begin(),dp.end(),it) - dp.begin(); dp[ind] = it; ans = max(ans, ind); } cout<<n-ans<<endl; return; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; t = 1; while (t--) { solve(); } 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...