Facebook
From Innocent Giraffe, 1 Year ago, written in C++.
Embed
Download Paste or View Raw
Hits: 113
  1. #include<bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define turbo ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  5. #define pii pair<int, int>
  6. #define pll pair<long long, long long>
  7. #define pb push_back
  8. #define f first
  9. #define s second
  10. #define hello cout<<"Hello World";
  11. #define endl "n"
  12. #define mid (l+r)/2
  13.  
  14. using namespace std;
  15.  
  16. int n, k;
  17.  
  18. deque<pll> q;
  19.  
  20. void dodaj(ll ans, ll index)
  21. {
  22.     while(!q.empty() and q.back().f >= ans)
  23.         q.pop_back();
  24.     q.push_back({ans, index});
  25.     while(!q.empty() and index-q.front().s >= k)
  26.         q.pop_front();
  27.     q.push_back({ans, index});
  28. }
  29.  
  30. int main()
  31. {
  32.     cin >> n >> k;
  33.     q.push_back({0, -1});
  34.     for(int i = 0; i < n; i++)
  35.     {
  36.         ll x;
  37.         cin >> x;
  38.         dodaj(x+q.front().f,i);
  39.     }
  40.     cout << q.front().f;
  41. }