Cod sursa(job #815546)

Utilizator UMihneaUngureanu Mihnea UMihnea Data 17 noiembrie 2012 10:32:35
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <deque>
#include <utility>
#define V first
#define I second

using namespace std;

int n,i,v,k;
long long int sol;
deque< pair<int,int> > Q;

int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<k;i++){
        scanf("%d",&v);
        while(Q.size()&&Q.back().V>=v)
        Q.pop_back();
        Q.push_back(make_pair(v,i));
    }
    for(;i<=n;i++)
    {
        scanf("%d",&v);
        while(Q.size()&&Q.back().V>=v)
        Q.pop_back();
        Q.push_back(make_pair(v,i));
        if(i-Q.front().I==k)
        Q.pop_front();
        sol+=Q.front().V;
    }
    printf("%lld",sol);
    return 0;
}