fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(1e5)+7;
  14. const ll inf = ll(1e18)+7;
  15.  
  16. int n , k , a[maxN];
  17. ll pre_dp[maxN] , cur_dp[maxN];
  18.  
  19. void solve(){
  20.     cin >> n >> k;
  21.     for (int i = 1 ; i <= n ; i++) cin >> a[i];
  22.     cur_dp[0] = +inf;
  23.     for (int i = 1 ; i <= n ; i++){
  24.         cur_dp[i] = min(cur_dp[i - 1] , 1ll * a[i]);
  25.     }
  26.     for (int t = 2 ; t <= k ; t++){
  27.         for (int i = 1 ; i <= n ; i++){
  28.             pre_dp[i] = cur_dp[i];
  29.             cur_dp[i] = -inf;
  30.         }
  31.         deque<int> dq;
  32.         for (int i = t ; i <= n ; i++){
  33.             while (dq.empty() == 0 && a[dq.back()] >= a[i]){
  34.                 int j = dq.back();
  35.                 pre_dp[i - 1] = max(pre_dp[i - 1] , pre_dp[j - 1]);
  36.                 cur_dp[i] = max(cur_dp[i] , pre_dp[j - 1] + 1ll * a[i]);
  37.                 dq.pop_back();
  38.             }
  39.             if (dq.empty() == 0){
  40.                 int j = dq.back();
  41.                 cur_dp[i] = max(cur_dp[i] , pre_dp[j - 1] + 1ll * a[j]);
  42.                 cur_dp[i] = max(cur_dp[i] , cur_dp[j]);
  43.             }
  44.             cur_dp[i] = max(cur_dp[i] , pre_dp[i - 1] + 1ll * a[i]);
  45.             dq.push_back(i);
  46.         }
  47.     }
  48.     cout << cur_dp[n] << "\n";
  49. }
  50.  
  51. #define name "N"
  52.  
  53. int main(){
  54.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  55.     if (fopen(name".INP" , "r")){
  56.         freopen(name".INP" , "r" , stdin);
  57.         freopen(name".OUT" , "w" , stdout);
  58.     }
  59.     int t = 1; //cin >> t;
  60.     while (t--) solve();
  61.     return 0;
  62. }
  63.  
  64.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000007
https://ideone.com/JQY6QF
language:
C++ (gcc 8.3)
created:
6 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!