fork download 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  4. #define lg2(n) (63-__builtin_clzll(n))
  5. #define mask(n) (1LL << (n))
  6. #define TASK ""
  7. #define openfile();  if( fopen(TASK".inp", "r")){freopen(TASK".inp", "r", stdin);freopen(TASK".out", "w", stdout);}
  8. #define lc(n) (n << 1)
  9. #define rc(n) ((n << 1) | 1)
  10.  
  11. #define fi first
  12. #define se second
  13. #define FOR(i, l, r, k) for( int i = l; i <= r; i += k)
  14. #define FOD(i, r, l, k) for( int i = r; i >= l; i -= k)
  15.  
  16. #define mii map<int,int>
  17. #define umi unordered_map<int, int>
  18. #define pii pair<int,int>
  19. #define vi vector<int>
  20.  
  21. using namespace std;
  22.  
  23. const int oo = 1e18;
  24. const int mod = 14062008;
  25. const int nmax = 300 + 8;
  26. const int base = 311;
  27.  
  28. int n, a[nmax], k, dp[151][nmax][nmax];
  29.  
  30. int sol(int l, int i, int j){
  31.     if(l > k){
  32.         return 0;
  33.     }
  34.     if(i >= j) return -oo;
  35.     if(!dp[l][i][j]) return dp[l][i][j];
  36.     int res = -oo;
  37.     res = max(res, sol(l + 1, i + 2, j) + abs(a[i] - a[i + 1]));
  38.     res = max(res, sol(l + 1, i + 1, j - 1) + abs(a[i] - a[j]));
  39.     res = max(res, sol(l + 1, i + 1, j - 2) + abs(a[i] - a[j]));
  40.     res = max(res, sol(l, i + 1, j));
  41.     res = max(res, sol(l, i, j - 1));
  42.     return dp[l][i][j] = res;
  43. }
  44.  
  45. main(){
  46.     fast;
  47.     openfile();
  48.     cin >> n >> k;
  49.     for(int i = 1; i <= n; ++i) cin >> a[i];
  50.     memset(dp, -1, sizeof dp);
  51.     cout << sol(1, 1, n);
  52. }
  53.  
Success #stdin #stdout 0.03s 115436KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ZyJVyH
language:
C++14 (gcc 8.3)
created:
2 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!