Cod sursa(job #1166401)

Utilizator heracleRadu Muntean heracle Data 3 aprilie 2014 15:56:52
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
#include <deque>

FILE* in;
FILE* out;
struct elem{
    int val;
    int tin;
};

std::deque<elem> a;

int main()
{
    in=fopen("deque.in","r");
    out=fopen("deque.out","w");

    int n,k,x;

    fscanf(in,"%d%d",&n,&k);

    long long rez=0;

    for(int i=1; i<=n; i++)
    {
        fscanf(in,"%d",&x);

        while(!a.empty() && x < a.back().val )
            a.pop_back();
        a.push_back(elem{x,i});

        if(i>=k)
        {
            rez+=a.front().val;
            if(a.front().tin==i-k+1)
                a.pop_front();
        }
    }
    fprintf(out,"%d",rez);

    return 0;
}