Cod sursa(job #1373404)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 4 martie 2015 18:27:25
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <iostream>
#include <list>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");

pair <int, int> paired;
deque <pair<int, int> > mydeck;
long long int n, k, x, i, sum;

int main()
{
    fin>>n>>k;
    for (i=1;i<=n;i++)
    {
        fin>>x;
        while (!mydeck.empty() && x<=mydeck.back().first)
            mydeck.pop_back();
        mydeck.push_back(make_pair(x,i));
        if (i>=k)
        {
            while (mydeck.back().second-mydeck.front().second>=k)
            {
                mydeck.pop_front();
            }
            sum+=mydeck.front().first;
        }
    }
    fout<<sum;

    return 0;
}