Cod sursa(job #1445746)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 30 mai 2015 22:40:53
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <stdio.h>
#include <deque>
using namespace std;

int N,K;
long long Sol;
deque < pair <int,int> > D;

int main()
{
    freopen("deque.in","r",stdin);
    scanf("%d %d",&N,&K);
     int X;

     for (int i = 1;i <= N;i++)
        {
            scanf("%d",&X);
            while(!D.empty() && D.back().first > X)
                D.pop_back();

            D.push_back(make_pair(X,i));

            if (D.front().second + K == i)
                D.pop_front();

            Sol += i < K ? 0 : D.front().first;
        }
    freopen("deque.out","w",stdout);
     printf("%d",Sol);
    return 0;
}