Submission #1277873

#TimeUsernameProblemLanguageResultExecution timeMemory
1277873k12_khoiRabbit Carrot (LMIO19_triusis)C++17
100 / 100
59 ms4436 KiB
#include <bits/stdc++.h> using namespace std; const int N=2e5+5; const int oo=1e9+1; int n,k; int a[N],dp[N][2]; namespace sub4 { int mx_bit,x,temp; int bit[N]; vector <int> ve; void rev_bitupdate(int u,int v) { for (int idx=u;idx>0;idx-=idx&-idx) bit[idx]=min(bit[idx],v); } int rev_bitget(int u) { int ans=oo; for (int idx=u;idx<=mx_bit;idx+=idx&-idx) ans=min(ans,bit[idx]); return ans; } void solve() { ve.clear(); a[0]=0; ve.push_back(0); for (int i=1;i<=n;i++) ve.push_back(a[i]-i*k); sort(ve.begin(),ve.end()); ve.resize(unique(ve.begin(),ve.end())-ve.begin()); mx_bit=ve.size(); for (int i=1;i<=mx_bit;i++) bit[i]=oo; dp[0][0]=0; dp[0][1]=oo; x=lower_bound(ve.begin(),ve.end(),a[0])-ve.begin()+1; rev_bitupdate(x,0); for (int i=1;i<=n;i++) { dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1; x=lower_bound(ve.begin(),ve.end(),a[i]-i*k)-ve.begin()+1; temp=rev_bitget(x)+i-1; dp[i][0]=temp; rev_bitupdate(x,temp-i); } cout << min(dp[n][0],dp[n][1]); } } int main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); cin >> n >> k; a[0]=0; for (int i=1;i<=n;i++) cin >> a[i]; sub4::solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...