Cod sursa(job #2615276)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 13 mai 2020 23:34:44
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include<cstdio>
#include<deque>
#include<queue>
using namespace std;
FILE*in=fopen("deque.in","r");
FILE*out=fopen("deque.out","w");
struct p
{
    int nr,poz;
};
p t;
deque<p> d;
int N,K,i,a;
long long s;
int main()
{
    fscanf(in,"%d%d",&N,&K);
    for(i=1;i<=N;i++)
    {
        fscanf(in,"%d",&a);
        while(!d.empty()&&d.back().nr>=a)
        {
            d.pop_back();
        }
        t.nr=a;
        t.poz=i;
        d.push_back(t);
        if(d.front().poz==i-K)
        {
            d.pop_front();
        }
        if(i>=K)
        {
            s=s+d.front().nr;
        }
    }
    fprintf(out,"%lld",s);
}