fork download 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. struct node{
  5.     int val,dp,minval;
  6. };
  7. int dp[100005][105],a[100005],n,k;
  8. int32_t main(){
  9.     ios_base::sync_with_stdio(0);
  10.     cin.tie(0);cout.tie(0);
  11.     cin >> n >> k;
  12.     for(int i = 1; i <= n ;i++){
  13.         cin >> a[i];
  14.     }
  15.     for(int i = 1; i <= n; i++) for(int j = 1; j <= k; j++) dp[i][j] = 1e16;
  16.     for(int i = 1; i <= n; i++) dp[i][1] = max(dp[i-1][1],a[i]);
  17.     for(int j = 2; j <= k; j++){
  18.         vector<node> st;
  19.         for(int i = j; i <= n; i++){
  20.             int minn = dp[i-1][j-1];
  21.             while(!st.empty() && st.back().val <= a[i]){
  22.                 minn = min(minn,st.back().dp); st.pop_back();
  23.             }
  24.             int minval = minn + a[i];
  25.             if(!st.empty()) minval = min(minval,st.back().minval);
  26.             st.push_back({a[i],minn,minval});
  27.             dp[i][j] = st.back().minval;
  28.         }
  29.     }
  30.     cout << dp[n][k];
  31. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ijmFdB
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!