Cod sursa(job #2458809)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 21 septembrie 2019 15:51:14
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 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() == 0 && 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;
}