Cod sursa(job #1045977)

Utilizator tavi.belu1994FMI Belu Andrei Octavian tavi.belu1994 Data 2 decembrie 2013 15:34:10
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <cstdio>
#include <deque>
FILE *f,*g;
using namespace std;

deque < long long > Q,NR;

int main()
{
    f = fopen("deque.in","r");
    g = fopen("deque.out","w");
    long long i,N,K,sum=0,x;
    fscanf(f,"%lld%lld\n",&N,&K);
    for(i=1 ; i<=N ; i++)
    {
        fscanf(f,"%lld\n",&x);
        while(!Q.empty() && x <= Q.back())
        {
            Q.pop_back();
            NR.pop_back();
        }
        Q.push_back(x);
        NR.push_back(i);
        if(NR.front() == i-K)
        {
            Q.pop_front();
            NR.pop_front();
        }
        if(i >= K)
        {
            sum += Q.front();
        }
    }
    fprintf(g,"%lld",sum);
    fclose(f);
    fclose(g);
    return 0;
}