Submission #83382

#TimeUsernameProblemLanguageResultExecution timeMemory
83382ToadDaveskiK blocks (IZhO14_blocks)C++14
0 / 100
245 ms81444 KiB
#include <bits/stdc++.h> #define ll long long #define fr first #define sc second using namespace std; deque <pair <ll,ll> > v; ll dp[101][100001],a[100001]; int main() { ll n,k,i,j; cin>>n>>k; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=n;i++) for(j=1;j<=k;j++) dp[j][i]=1e9; for(i=1;i<=k;i++) { v.clear(); for(j=1;j<=n;j++) { ll s=dp[i-1][j-1]; if (j<i) { dp[i][j]=1e9; continue; } while(!v.empty() && v.front().fr<=a[j]) { //cout<<v.front().first<<" delete "<<v.front().sc<<endl; s=min(s,v.front().sc); v.pop_front(); } if (!v.empty() && v.front().fr+v.front().sc<=s+a[j]) dp[i][j]=v.front().fr+v.front().sc; else { dp[i][j]=s+a[j]; v.push_front({a[j],s}); //cout<<v.front().first<<" add "<<v.front().sc<<endl; } //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; } } cout<<dp[k][n]; 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...