• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Apr 18th, 2019 82 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.
Not a member of Pastebin yet?