Cod sursa(job #363757)

Utilizator andreitheo87Teodorescu Andrei-Marius andreitheo87 Data 14 noiembrie 2009 17:18:45
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<iostream>
#include<list>
using  namespace std;
list<int> nr,pos;
int k;
void baga(int x,int posi)
{
    while( nr.size() && ( nr.back() >= x ) )
    {
        nr.pop_back();
        pos.pop_back();
    }
    nr.push_back(x);
    pos.push_back(posi);
    if( posi - pos.front() >= k )
    {
        nr.pop_front();
        pos.pop_front();
    }
}
int minim()
{
    return nr.front();
}
int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    int n,x;
    scanf("%d %d",&n,&k);
    for(int i=0; i<k; i++)
    {
        scanf("%d",&x);
        baga(x,i);
    }
    long long rez = minim();
    for(int i=k; i<n; i++)
    {
        scanf("%d",&x);
        baga(x,i);
        rez+=minim();
    }
    printf("%lld\n",rez);
	return 0;
}