fork(4) download
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int inf = 1e9 + 5;
  6. const int N = 1e5 + 5;
  7.  
  8. int n, k, a[N], dp[N], bef[N];
  9. pair < int, int > p[N];
  10.  
  11. int main () {
  12.  
  13. cin >> n >> k;
  14.  
  15. for(int i = 1; i <= n; i++) {
  16. cin >> a[i];
  17. bef[i] = max(bef[i - 1], a[i]);
  18. }
  19.  
  20. for(int j = 2; j <= k; j++) {
  21. int sz = 0;
  22. for(int i = 1; i <= n; i++) {
  23. int ans = j <= i ? bef[i - 1] : inf;
  24. bef[i - 1] = dp[i - 1];
  25. while(sz and a[i] >= p[sz - 1].first)
  26. ans = min(ans, p[--sz].second);
  27. if(!sz or a[i] + ans < p[sz - 1].first + p[sz - 1].second)
  28. p[sz++] = make_pair(a[i], ans);
  29. dp[i] = p[sz - 1].first + p[sz - 1].second;
  30. }
  31. bef[n] = dp[n];
  32. }
  33.  
  34. cout << bef[n] << endl;
  35.  
  36. return 0;
  37.  
  38. }
  39.  
Success #stdin #stdout 0s 5052KB
stdin
Standard input is empty
stdout
0