Cod sursa(job #3368789)

Utilizator Andrei563Secara Andrei Tudor Andrei563 Data 15 octombrie 2026 19:27:02
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <vector>
#include <deque>
#define int long long

using namespace std;
ifstream cin ("deque.in");
ofstream cout ("deque.out");

signed main ()
{
  int n,k;
  cin >> n >> k;
  deque<int> dq;
  vector <int> rez(n+1);
  vector<int> v(n+1);
  for (int i=1;i<=n;++i)
  {
    cin >> v[i];
  }
  for (int i=1;i<=n;++i)
  {
    while (!dq.empty() && v[dq.back()]>=v[i])
      dq.pop_back();
    dq.push_back(i);
    while (!dq.empty() && dq.front()<=i-k)
      dq.pop_front();
    rez[i]=v[dq.front()];
  }
  int s=0;
  for (int i=1;i<=n;++i)
  {
    if (i>=k)
      s+=rez[i];
  }
  cout << s;

}