Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- 6 3
- 4 3 2 5 6 4
- {idx,val} idx -indice val-cost
- {0,0}
- sol=4+0
- it={1,4}
- push({1,4})
- {0,0} {1,4}
- sol=3+0=3
- {2,3}
- pop({1,4})
- push({2,3})
- {0,0} {2,3}
- sol=2+0=2
- pop({2,3})
- push({3,2})
- {0,0} {3,2}
- sol=5+2
- pop({0,0})
- {3,2} {4,7}
- sol=6+2=8
- {3,2}{4,7}{5,8}
- sol=4+2
- pop({5,8})
- pop({4,7})
- push({6,6})
- {3,2}{6,6}
- */
- // Popa Bogdan Ioan, Colegiul National Aurel Vlaicu Orastie, clasa a 10-a
- #include <bits/stdc++.h>
- #define ll long long
- using namespace std;
- ifstream fin("zen.in");
- ofstream fout("zen.out");
- struct Zen
- {
- int idx;
- ll val;
- };
- deque<Zen>DQ;
- int n,K;
- ll sol;
- int val;
- int i;
- void update(ll val, int idx)
- {
- Zen it={idx,val};
- while(!DQ.empty() && DQ.back().val>=it.val)
- DQ.pop_back();
- DQ.push_back(it);
- }
- ll query(int idx)
- {
- if(idx>K)
- if(DQ.front().idx<idx-K)
- DQ.pop_front();
- return DQ.front().val;
- }
- int main()
- {
- fin>>n>>K;
- DQ.push_back({0,0});
- for(i=1;i<=n;i++)
- {
- fin>>val;
- sol=val+query(i);
- update(sol,i);
- }
- fout<<sol<<"\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement