제출 #556108

#제출 시각아이디문제언어결과실행 시간메모리
556108HeatDroppaStove (JOI18_stove)C++14
50 / 100
1095 ms3268 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int lim=1e5+4; const ll inf=1e18; ll dp_new[lim]; ll dp_old[lim]; int t[lim]; int n,k; void solve(int l,int r,int optl,int optr) { if(l>r) return ; int med=(l+r)>>1; pair<ll,int> bst={inf,-1}; for(int i=optl;i<=min(med,optr);++i) bst=min(bst,{dp_old[i-1]+t[med]-t[i]+1,i}); dp_new[med]=bst.first; solve(l,med-1,optl,bst.second); solve(med+1,r,bst.second,optr); } int main() { //ios_base::sync_with_stdio(false); //cin.tie(0),cout.tie(0); cin>>n>>k; for(int i=1;i<=n;++i) cin>>t[i], dp_old[i]=t[i]-t[1]+1; for(int i=2;i<=k;++i) solve(i,n,i,n), swap(dp_old,dp_new); cout<<dp_old[n]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...