Cod sursa(job #2460139)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 22 septembrie 2019 20:49:02
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <utility>

using namespace std;

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

int main()
{
    deque<pair<int,int>> v;
    int n, k, i, val, s = 0;
    pair<int,int> x;

    in >> n >> k;

    for(i = 1; i <= n; i++)
    {
        in >> val;

        x.first = val;
        x.second = i;

        while(!v.empty() && val <= v.back().first)
                v.pop_back();

        v.push_back(x);

        if(v.front().second == i-k)
                v.pop_front();

        if(i >= k)
                s += v.front().first;

        //cout << val << ' ' << s << '\n';

    }

    out << s << '\n';

    return 0;
}