fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ============ TYPEDEFS & MACROS ============
  5. typedef long long ll;
  6. #define all(x) x.begin(), x.end()
  7. #define ln "\n"
  8. #define Omar_Salah               \
  9. ios::sync_with_stdio(false); \
  10. cin.tie(NULL);
  11. #define Read  \
  12. freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  13. const int MY_MOD = 1e9 + 7;
  14. // ============ MAIN SOLUTION ============
  15. int n , k;
  16. ll sum;
  17. vector<int> v;
  18. int dp[300001][11];
  19. ll rec(int i , int k) {
  20.  
  21.     if (i == n) {
  22.         return 0;
  23.     }
  24.  
  25.     int ch1  = INT_MAX , ch2 = INT_MAX;
  26.     // choise 1 leave
  27.     ch1 = v[i];
  28.     // choise 2 take the menimum of them--> replace with right or left
  29.     int left  = ((i - 1 >= 0 && k != 0) ? v[i - 1] : INT_MAX);
  30.     int right = ((i + 1 < n  && k != 0 )?  v[i + 1] : INT_MAX);
  31.  
  32.     ch2 = min(left, right);
  33.  
  34.     dp[i][k] = min(ch1 , ch2)  + rec(i + 1 , k - (ch2 < ch1 ? 1 : 0));
  35.  
  36.     return dp[i][k];
  37. }
  38. void solve()
  39. {
  40.     memset(dp, -1, sizeof(dp));
  41.      cin >> n >> k;
  42.     v.resize(n);
  43.     sum = 0;
  44.     for (int i = 0; i < n; i++) {
  45.         cin >> v[i];
  46.         sum += v[i];
  47.     }
  48.     if (k == 0) {
  49.         cout << sum << endl;
  50.         return;
  51.     }
  52.     cout << rec(0, k) << endl;
  53. }
  54. int main()
  55. {
  56.     Omar_Salah
  57.     //Read
  58.     int t = 1;
  59.     cin >> t;
  60.     while (t--)
  61.     {
  62.         solve();
  63.     }
  64.  
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 16388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/BPtUX5
language:
C++14 (gcc 8.3)
created:
1 day 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!