Cod sursa(job #1097425)

Utilizator kiralalaChitoraga Dumitru kiralala Data 3 februarie 2014 13:47:24
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <deque>
#include<utility>
#define mp(x,y) make_pair(x,y)

using namespace std;

FILE* f=freopen("deque.in","r",stdin);
FILE* o=freopen("deque.out","w",stdout);

typedef pair<int,int> pr;

deque<pr> dq;

int n,k;

void Insert(int x, int p)
{
    while(!dq.empty()&&dq.back().first>=x)
        dq.pop_back();
    dq.push_back(mp(x,p));
}

int main()
{
    scanf("%d%d",&n,&k);
    int x;
    for(int i=0;i<k-1;++i) {
        scanf("%d",&x);
        Insert(x,i);
    }
    int sum=0;
    for(int i=k-1;i<n;++i)
    {
        while(!dq.empty()&&dq.front().second<=i-k)
            dq.pop_front();
        scanf("%d",&x);
        Insert(x,i);
        sum+=dq.front().first;
    }

    printf("%d",sum);

    return 0;
}