Cod sursa(job #2546447)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 14 februarie 2020 10:37:28
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
int v[100005];
int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    int n,i,k;
    deque<int>deq;
    deque<int>poz;
    int sum=0;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    {scanf("%d",&v[i]);
     if(deq.empty())
     {
         deq.push_back(v[i]);
         poz.push_back(i);
         continue;
     }
      if(i<=k)
      {
          while(!deq.empty()&&deq.back()>v[i])
          {
              deq.pop_back();
              poz.pop_back();
          }
          deq.push_back(v[i]);
          poz.push_back(i);
          if(i==k)
          {
             sum+=deq.front();
          }
      }
      else
      {

          while(!deq.empty()&&deq.back()>v[i])
          {
              deq.pop_back();
              poz.pop_back();
          }
          deq.push_back(v[i]);
          poz.push_back(i);
          if(poz.front()==(i-k))poz.pop_front(),deq.pop_front();
          sum+=deq.front();
      }
    }
    cout<<sum;
    return 0;
}