fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define ll long long
  7. #define ull unsigned long long
  8. #define f first
  9. #define ith_op second
  10. #define sort_all(v) sort(v.begin(), v.end())
  11.  
  12. #define ya_sayed_ya_badawy            \
  13.     ios_base::sync_with_stdio(false); \
  14.     cin.tie(NULL);
  15.  
  16. const int MAX = 2e5 + 50;
  17. const int MAX_N = 1e5 + 50;
  18. int MOD = 1e9 + 7;
  19. const int OO = 1e18;
  20. const double EPS = (double)1e-9;
  21.  
  22. int add(ll a, ll b)
  23. {
  24.     return ((a % MOD) + (b % MOD)) % MOD;
  25. }
  26.  
  27. int sub(ll a, ll b)
  28. {
  29.     return ((a % MOD) - (b % MOD) + MOD) % MOD;
  30. }
  31.  
  32. int mul(ll a, ll b)
  33. {
  34.     return ((a % MOD) * (b % MOD)) % MOD;
  35. }
  36.  
  37. int fp(ll base, ll pow)
  38. {
  39.     if (pow == 0)
  40.     {
  41.         return 1;
  42.     }
  43.  
  44.     ll res = fp(base, pow / 2);
  45.  
  46.     if (pow % 2 == 0)
  47.     {
  48.         return mul(res, res);
  49.     }
  50.  
  51.     return mul(base, mul(res, res));
  52. }
  53.  
  54. int inv(ll up, ll down)
  55. {
  56.     return mul(up, fp(down, MOD - 2));
  57. }
  58.  
  59. int n, k, x;
  60. int arr[MAX];
  61.  
  62. int mem[MAX][3][25];
  63. int vis[MAX][3][25];
  64. int tc = 1;
  65.  
  66. int dp(int idx, int type, int k)
  67. {
  68.  
  69.     if (idx == n)
  70.     {
  71.         if (k != 0)
  72.         {
  73.             return -OO;
  74.         }
  75.         return 0;
  76.     }
  77.  
  78.     int &ret = mem[idx][type][k];
  79.  
  80.     if (vis[idx][type][k] == tc)
  81.     {
  82.         return ret;
  83.     }
  84.  
  85.     if (type == 0)
  86.     {
  87.         ret = max(dp(idx, 1, k), dp(idx + 1, 0, k));
  88.         if (k)
  89.         {
  90.             ret = max(ret, dp(idx + 1, 0, k - 1));
  91.         }
  92.     }
  93.     else if (type == 1)
  94.     {
  95.         ret = max(dp(idx, 2, k), (arr[idx] - x) + dp(idx + 1, 1, k));
  96.         if (k)
  97.         {
  98.             ret = max(ret, (arr[idx] + x) + dp(idx + 1, 1, k - 1));
  99.         }
  100.     }
  101.     else if (type == 2)
  102.     {
  103.         ret = dp(idx + 1, 2, k);
  104.         if (k)
  105.         {
  106.             ret = max(ret, dp(idx + 1, 2, k - 1));
  107.         }
  108.     }
  109.  
  110.     vis[idx][type][k] = tc;
  111.  
  112.     return ret;
  113. }
  114.  
  115. void solve()
  116. {
  117.     cin >> n >> k >> x;
  118.  
  119.     for (int i = 0; i < n; i++)
  120.     {
  121.         cin >> arr[i];
  122.     }
  123.  
  124.     cout << dp(0, 0, k);
  125.     tc++;
  126. }
  127.  
  128. signed main()
  129. {
  130.     ya_sayed_ya_badawy int t = 1;
  131.  
  132.     cin >> t;
  133.  
  134.     while (t--)
  135.     {
  136.         solve();
  137.         if (t != 0)
  138.         {
  139.             cout << endl;
  140.         }
  141.     }
  142.     return 0;
  143. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eTVVpW
language:
C++14 (gcc 8.3)
created:
4 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!