Advertisement
Guest User

Untitled

a guest
Apr 18th, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. /**
  2. 6 3
  3. 4 3 2 5 6 4
  4. {idx,val} idx -indice val-cost
  5. {0,0}
  6. sol=4+0
  7. it={1,4}
  8. push({1,4})
  9. {0,0} {1,4}
  10. sol=3+0=3
  11. {2,3}
  12. pop({1,4})
  13. push({2,3})
  14. {0,0} {2,3}
  15. sol=2+0=2
  16. pop({2,3})
  17. push({3,2})
  18. {0,0} {3,2}
  19. sol=5+2
  20. pop({0,0})
  21. {3,2} {4,7}
  22. sol=6+2=8
  23. {3,2}{4,7}{5,8}
  24. sol=4+2
  25. pop({5,8})
  26. pop({4,7})
  27. push({6,6})
  28. {3,2}{6,6}
  29. */
  30. // Popa Bogdan Ioan, Colegiul National Aurel Vlaicu Orastie, clasa a 10-a
  31. #include <bits/stdc++.h>
  32. #define ll long long
  33. using namespace std;
  34. ifstream fin("zen.in");
  35. ofstream fout("zen.out");
  36. struct Zen
  37. {
  38. int idx;
  39. ll val;
  40. };
  41. deque<Zen>DQ;
  42. int n,K;
  43. ll sol;
  44. int val;
  45. int i;
  46. void update(ll val, int idx)
  47. {
  48. Zen it={idx,val};
  49. while(!DQ.empty() && DQ.back().val>=it.val)
  50. DQ.pop_back();
  51. DQ.push_back(it);
  52. }
  53. ll query(int idx)
  54. {
  55. if(idx>K)
  56. if(DQ.front().idx<idx-K)
  57. DQ.pop_front();
  58. return DQ.front().val;
  59. }
  60. int main()
  61. {
  62. fin>>n>>K;
  63. DQ.push_back({0,0});
  64. for(i=1;i<=n;i++)
  65. {
  66. fin>>val;
  67. sol=val+query(i);
  68. update(sol,i);
  69. }
  70. fout<<sol<<"\n";
  71. return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement