Cod sursa(job #1097432)

Utilizator kiralalaChitoraga Dumitru kiralala Data 3 februarie 2014 13:54:47
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 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<long long,int> pr;

deque<pr> dq;

int n,k;

void Insert(long long 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);
    long long x;
    for(int i=0;i<k;++i) {
        scanf("%lld",&x);
        Insert(x,i);
    }
    long long sum=0;
    for(int i=k;i<n;++i)
    {
        sum+=dq.front().first;
        while(!dq.empty()&&dq.front().second<=i-k)
            dq.pop_front();
        scanf("%lld",&x);
        Insert(x,i);
    }

    printf("%lld",sum+dq.front().first);

    return 0;
}