Cod sursa(job #2239742)

Utilizator HaesteinnSabau Florin Vlad Haesteinn Data 11 septembrie 2018 19:16:09
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

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

int main()
{
    deque< pair<int,int> > dq;
    int n,k;
    long long smin;
    fin>>n>>k;
    int tmp;
    for(int i=0;i<n;i++)
    {
        fin>>tmp;
        while(dq.size()>0&&dq.back().first>=tmp)
            dq.pop_back();
        dq.push_back(make_pair(tmp,i));
        if(dq.front().second == i - k)
            dq.pop_front();
        if(i >= k-1)
            smin+=dq.front().first;
    }
    fout<<smin;

    return 0;
}