Submission #1261433

#TimeUsernameProblemLanguageResultExecution timeMemory
1261433one_unknownRabbit Carrot (LMIO19_triusis)C++20
0 / 100
1 ms1036 KiB
#include <bits/stdc++.h> using namespace std; #define int long long using vi = vector<int>; using vpii = vector<pair<int,int>>; #define MOD 1000000007 #define all(arr) arr.begin(), arr.end() #define take(arr) for(auto &x : arr) cin >> x; #define print(arr) for(auto &x : arr) cout << x << " "; cout << "\n"; #define out(val) cout<<((val == 1) ? "YES" : "NO")<<endl; void solve() { int n,m; cin>>n>>m; vector<int> arr(n+1); vector<int> a; for(int i = 1; i<=n; ++i){ cin>>arr[i]; if(arr[i] <= (i * m)){ arr[i] -= ((i) * m); a.push_back(arr[i]); } } reverse(all(a)); int k = a.size(); const int inf = 1e18; vector<int> dp(k+1, inf); dp[0] = -inf; for(int i = 1; i<=k; ++i){ int l = upper_bound(all(dp), a[i]) - dp.begin(); if(dp[l-1] <= a[i] and dp[l] > a[i]){ dp[l] = a[i]; } } int mx = 0; for(int i = 1; i<=k; ++i){ if(dp[i] != inf){ mx = i; } } cout<<n - mx<<endl; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int 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...