SHARE
TWEET

Untitled

a guest Apr 18th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top