제출 #483035

#제출 시각아이디문제언어결과실행 시간메모리
483035keertanRabbit Carrot (LMIO19_triusis)C++17
100 / 100
27 ms5304 KiB
/** * If you live in an imaginary world when your imaginary situation is encountered in * real situation you can't enjoy it because you have to do pending work. * {This pending work appeared because you wasted that time on your useless * imaginary thinking.} */ #include<bits/stdc++.h> using namespace std; //#define int int64_t #define all(x) x.begin(),x.end() #define all1(x) x.rbegin(),x.rend() #define sz(x) (int32_t)(x.size()) const int N=1e2; void solve(){ int n,m; cin>>n>>m; vector<int>z(n+1); for (int i=1;i<=n;i++){cin>>z[i];} vector<int> con; for (int i=1;i<=n;i++){ if (i*m>=z[i]){ con.push_back(i*m-z[i]); } } vector<int> dp; for (int &it:con){ int pos=upper_bound(all(dp),it)-dp.begin(); if (pos==sz(dp)){ dp.push_back(it); } else{ dp[pos]=it; } } cout<<n-sz(dp); } int32_t main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int tq=1; //cin>>tq; for (;tq;tq--){solve();} } //is a brute-force possible? //think greedier, make more assumptions // if you find a solution using a loop to decrease complexity use bs //stuck for more than 5 minutes? move on
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...