Advertisement
Guest User

Untitled

a guest
Feb 24th, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <deque>
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <math.h>
  8. #include <string>
  9. #include <set>
  10. #include <iomanip>
  11. #include <bitset>
  12. #include <random>
  13. #include <unordered_map>
  14. #include <unordered_set>
  15. using namespace std;
  16. #define pb push_back
  17. #define ll long long
  18. #define mp make_pair
  19. #define fst first
  20. #define snd second
  21. #define ld long double
  22. #define mt make_tuple
  23. using namespace std;
  24. const int N = 1e5 + 5;
  25. ll a[N] , dp[N];
  26. ll sum = 0;
  27. multiset<ll> kek;
  28. int main()
  29. {
  30. ios_base::sync_with_stdio(0);
  31. cin.tie(0);
  32. cout.tie(0);
  33. int n , c;
  34. cin >> n >> c;
  35. for(int i = 0; i < n; i++)
  36. {
  37. cin >> a[i];
  38. }
  39. for(int i = 0; i < n; i++)
  40. {
  41. sum += a[i];
  42. if (i >= c)
  43. {
  44. sum -= a[i - c];
  45. auto it = kek.find(a[i - c]);
  46. if(it != kek.end()) kek.erase(it);
  47. }
  48. kek.insert(a[c]);
  49. dp[i + 1] = dp[i] + a[i];
  50. ll p = dp[i - c + 1] - *kek.begin();
  51. if (i > c - 2) dp[i + 1] = min(dp[i + 1], sum + p);
  52. }
  53. cout << dp[n] << "\n";
  54. return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement