Submission #1247591

#TimeUsernameProblemLanguageResultExecution timeMemory
1247591papauloRabbit Carrot (LMIO19_triusis)C++20
100 / 100
19 ms5820 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 200200 int a[MAXN]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, m; cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; int ans=0; vector<pair<int, int>> vec; for(int i=1;i<=n;i++) { int mx=i*m; a[i]-=mx; if(a[i]>0) { ans++; continue; } a[i]*=-1; vec.push_back({a[i], i}); } vector<pair<int, int>> lens; for(auto x : vec) { auto p = lower_bound(lens.begin(), lens.end(), x); if(p==lens.end()) lens.push_back(x); else *p=x; } ans+=vec.size()-lens.size(); cout << ans << endl; 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...