Cod sursa(job #2368326)

Utilizator danhHarangus Dan danh Data 5 martie 2019 15:31:13
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

ifstream fin("deque.in");
ofstream fout("deque.out");

deque<pair<int, int> > dq;

int main()
{
    int n, k, i, x, sum = 0;
    fin>>n>>k;
    fin>>x;
    dq.push_front(make_pair(x, 1));
    for(i=2; i<=k; i++)
    {
       fin>>x;
       while(x < dq.back().first)
       {
           dq.pop_back();
       }
       dq.push_back(make_pair(x, i));
    }

    sum += dq.front().first;
    dq.pop_front();

    int lcrt = k-1;

    for(i=k+1; i<=n; i++)
    {
        fin>>x;
        while(x < dq.back().first)
        {
            dq.pop_back();
        }

        dq.push_back(make_pair(x, i));

        if(dq.front().second < i - k + 1)
        {
            dq.pop_front();
        }
        sum += dq.front().first;


    }

    fout<<sum;

    fin.close();
    fout.close();
    return 0;
}