Cod sursa(job #2264979)

Utilizator buhaidarius@gmail.comBuhai Darius [email protected] Data 20 octombrie 2018 14:13:51
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
//
//  main.cpp
//  Deque
//
//  Created by Darius Buhai on 20/10/2018.
//  Copyright © 2018 Darius Buhai. All rights reserved.
//

#include <iostream>
#include <deque>
#include <fstream>

using namespace std;

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

int n, k, x;
long long s;

deque<pair<int, int>> v;

void rez_deque()
{
    fin>>n>>k;
    for(long i=0;i<n;i++){
        fin>>x;
        while(!v.empty() && v.back().second>x)
            v.pop_back();
        pair<int,int> xx(i,x);
        v.push_back(xx);
        if(i>k-2)
            s+=v.front().second;
        if(i-v.front().first>=k-1)
            v.pop_front();
    }
    fout<<s;
}

int main() {
    rez_deque();
    return 0;
}