Cod sursa(job #2044343)

Utilizator vlad6001Pintilie Vlad vlad6001 Data 21 octombrie 2017 09:32:06
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <deque>
using namespace std;

ifstream cin("deque.in");
ofstream cout("deque.out");

struct Punct
{
    long long val, timp;
}x;

long long nr, k, val, total;
deque <Punct> deq;

int main()
{
    cin >> nr >> k;

    for(int i=1; i <= nr; i++)
    {
        cin >> val;
        if(deq.empty() == false)
        {
            x = deq.back();
            if(i-x.timp == k)
            deq.pop_back();
        }

        if(deq.empty() == false)
        x = deq.front();
        while(x.val > val && deq.empty() == false)
        {
            deq.pop_front();
            x = deq.front();
        }
        deq.push_front({val, i});

        if(i >= k)
        total += deq.back().val;
    }
    cout << total;
}