Cod sursa(job #2045910)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 23 octombrie 2017 01:21:28
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <deque>

std::ifstream f("deque.in");
std::ofstream g("deque.out");
int v[5000000];
std::deque <int> minDq;

long long rez;
int main()
{
    int N, K;
    f>>N>>K;

    for(int i=1; i<=N; i++)
        f>>v[i];


    int i;
    for(i=1; i<=K; i++) {
        while(!minDq. empty() && v [minDq. back()] >= v[i])
            minDq. pop_back();

        minDq. push_back(i);
    }
    rez += v[minDq. front()];


    for(; i<=N; i++) {
        if(!minDq.empty() && minDq.front() <= i-K)
            minDq.pop_front();

        while(!minDq. empty() && v [minDq. back()] >= v[i])
            minDq. pop_back();

        minDq. push_back(i);

        rez += v[minDq. front()];
    }

    g<<rez;

    return 0;
}