fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6.  
  7. int minPartitionScore(vector<int>& a, int k)
  8. {
  9.     int n = a.size();
  10.     vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, 1e17));
  11.  
  12.     dp[n][0] = 0;
  13.  
  14.     for(int w = 1; w <= k; ++w)
  15.     {
  16.         stack<vector<ll>> st{};// stores (max in range, min value dp[range][w - 1], min value of max(a[i + 1 + j]) + dp[j][w - 1])
  17.         for(int i = n - 1; i >= 0; --i)
  18.         {
  19.             ll mn = dp[i + 1][w - 1];
  20.             while(!st.empty() && st.top()[0] <= a[i])
  21.             {
  22.                 mn = min(mn, st.top()[1]);
  23.                 st.pop();
  24.             }
  25.  
  26.             ll y = min(a[i] + mn, st.empty() ? (ll) 1e17 : st.top()[2]);// update the minimum, this is the value we need after adjustments
  27.             st.push({a[i], mn, y});
  28.             dp[i][w] = y;
  29.         }
  30.     }
  31.  
  32.     return dp[0][k];
  33. }
  34.  
  35.  
  36. signed main()
  37. {
  38.  
  39.     vector<int> a{2, 5, 4, 3, 7, 1, 6, 8};
  40.  
  41.     cout<<minPartitionScore(a, 3)<<"\n";
  42. }
  43.  
  44.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
15
https://ideone.com/33chdv
language:
C++ (gcc 8.3)
created:
3 days 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!