fork download
copy 
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <map>
  7. #include <set>
  8. #include <queue>
  9. #include <cmath>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include <iomanip>
  13. #include <deque>
  14. #include <chrono>
  15. #include <cassert>
  16. #include <bitset>
  17. #include <random>
  18.  
  19. using namespace std;
  20.  
  21. typedef long long li;
  22. typedef  long double ld;
  23. const li MAX = 3e5 + 20;
  24.  
  25. li inf = (li)1e15;
  26. li mod = (li)998244353;
  27.  
  28. li dp1[MAX], dp2[MAX], p[MAX], cool[MAX];
  29. li n, k, a[MAX];
  30.  
  31. void solve() {
  32.     cin >> n >> k;
  33.     for (int i = 1; i <= n; i++) {
  34.         cin >> a[i];
  35.     }
  36.  
  37.     vector<li> cur;
  38.     for (int i = 1; i <= n; i++) {
  39.         while (cur.size() && a[cur.back()] < a[i]) cur.pop_back();
  40.         if (cur.size()) p[i] = cur.back();
  41.         cur.push_back(i);
  42.     }
  43.     li cur_max = a[1];
  44.     dp1[0] = inf;
  45.     dp2[0] = inf;
  46.     for (int i = 1; i <= n; i++) {
  47.         cur_max = max(cur_max, a[i]);
  48.         dp1[i] = cur_max;
  49.     }
  50.  
  51.     for (int j = 2; j <= k; j++) {
  52.         vector<li> cur = { 0 };
  53.         for (int i = 1; i <= n; i++) {
  54.             dp2[i] = inf;
  55.             li uk1 = -1, uk2 = cur.size();
  56.             while (uk2 - uk1 > 1) {
  57.                 li mid = (uk2 + uk1) / 2;
  58.                 if (cur[mid] >= p[i]) uk2 = mid;
  59.                 else uk1 = mid;
  60.             }
  61.             if (uk2 != cur.size()) dp2[i] = min(dp2[i], dp1[cur[uk2]] + a[i]);
  62.             while (cur.size() && dp1[cur.back()] > dp1[i]) cur.pop_back();
  63.             cur.push_back(i);
  64.         }
  65.         for (int i = 1; i <= n; i++) {
  66.             dp2[i] = min(dp2[i], dp2[p[i]]);
  67.         }
  68.  
  69.         for (int i = 0; i <= n; i++) dp1[i] = dp2[i];
  70.     }
  71.     cout << dp1[n];
  72. }
  73.  
  74. int main() {
  75.     mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  76.     ios::sync_with_stdio(0);
  77.     li q;
  78.     q = 1;
  79.     while (q--) solve();
  80.  
  81.     return 0;
  82. }
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000
https://ideone.com/zBTS7j
language:
C++14 (gcc 8.3)
created:
3 years 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!