fork download
copy 
  1. /*
  2.     @author longvuuuu
  3. */
  4. #include <bits/stdc++.h>
  5. #define taskname ""
  6. #define ll long long
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. using namespace std;
  11. const ll NMAX = (ll)1e18;
  12. const ll INF = LLONG_MIN;
  13. vector<ll> a;
  14. vector<vector<vector<ll>>> dp;
  15. int main()
  16. {
  17.     ios_base::sync_with_stdio(0);
  18.     cin.tie(0);cout.tie(0);
  19.     if(fopen((string(taskname) + ".inp").c_str(), "r") != NULL) {
  20.         freopen((string(taskname) + ".inp").c_str(), "r", stdin);
  21.         freopen((string(taskname) + ".out").c_str(), "w", stdout);
  22.     }
  23.  
  24.     int n, k;
  25.     cin >> n >> k;
  26.     a.assign(n + 3, 0);
  27.     for(int i = 1; i <= n; i++)
  28.         cin >> a[i];
  29.     dp.assign(n + 3, vector<vector<ll>>(n + 3, vector<ll>(k + 1, INF)));
  30.     for(int x = 1; x <= n + 1; x++)
  31.         for(int y = x - 1; y <= n; y++)
  32.             dp[x][y][0] = 0;
  33.     for(int i = 2; i <= n; i++)
  34.         for(int x = 1; x + i - 1 <= n; x++)
  35.         {
  36.             int y = x + i - 1;
  37.             for (int z = 1; z <= k && i >= 2 * z; z++)
  38.             {
  39.                 if (dp[x + 2][y][z - 1] != INF)
  40.                     dp[x][y][z] = max(dp[x][y][z], dp[x + 2][y][z - 1] + llabs(a[x] - a[x + 1]));
  41.                 if (dp[x][y - 2][z - 1] != INF)
  42.                     dp[x][y][z] = max(dp[x][y][z], dp[x][y - 2][z - 1] + llabs(a[y - 1] - a[y]));
  43.                 if (dp[x + 1][y - 1][z - 1] != INF)
  44.                     dp[x][y][z] = max(dp[x][y][z], dp[x + 1][y - 1][z - 1] + llabs(a[x] - a[y]));
  45.                 dp[x][y][z] = max(dp[x][y][z], dp[x + 1][y][z]);
  46.                 dp[x][y][z] = max(dp[x][y][z], dp[x][y - 1][z]);
  47.             }
  48.         }
  49.  
  50.     ll res = dp[1][n][k];
  51.     if (res <= INF / 2) cout << -1 << '\n';
  52.     else cout << res << '\n';
  53. }
  54.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6 2
1 3 10 2 1 4
stdout
copy 
12
https://ideone.com/R8hhbq
language:
C++ (gcc 8.3)
created:
2 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!