Submission #1097983

#TimeUsernameProblemLanguageResultExecution timeMemory
1097983hippo123Rabbit Carrot (LMIO19_triusis)C++17
0 / 100
2 ms1884 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pr pair<int, int> #define prr pair<pr, int> #define f first #define s second #define pr pair<int, int> #define pb push_back const int ndim=2e5+1; vector<int> par(ndim); vector<int> psize(ndim); int main(){ int n, m; cin>>n>>m; vector<int> d(n+1); for (int i=1; i<=n; i++) cin>>d[i]; d[0]=0; multiset<pr> st; vector<int> par(n+1); for (int i=0; i<=n; i++) par[i]=i; st.insert({d[0], 0}); for (int i=1; i<=n; i++){ auto it=st.upper_bound({d[i], i}); if(it==st.end()) { it--; par[i]=it->s; st.insert({d[i], i}); } else{ st.erase(it); st.insert({d[i], i}); it=st.lower_bound({d[i], i}); it--; par[i]=it->s; } } vector<int> dp(n+1, 0); vector<int> ds(n+1); ds[0]=d[0]; int res=0; for (int i=1; i<=n; i++){ if(d[i]-ds[i-1]>m || d[i]-ds[par[i]]>m*(i-par[i])){ //cout<<" i= "<<i<<endl; //cout<<" d[i]-ds[i-1]/m/ d[i]-ds[par[i]]/m*(i-par[i]="<<d[i]-ds[i-1]<<" "<<m<<" "<< d[i]-ds[par[i]]<<" "<<m*(i-par[i])<<endl; ds[i]=min(ds[i-1]+m, m*(i-par[i])+ds[par[i]]); res++; } else ds[i]=d[i]; } cout<<res<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...