Cod sursa(job #2543648)

Utilizator MariusblockMoga Marius-Ioan Mariusblock Data 11 februarie 2020 13:19:12
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;

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

struct nr{
    long long val,poz;
};

deque<nr> v;

int main()
{
    int i,n,k;
    long long S = 0;
    fin>>n>>k;
    nr aux;
    for(i = 1; i <= n; i++){
        fin>>aux.val;
        aux.poz = i;
        if(v.empty()){
            v.push_back(aux);
        }else{
            while(!v.empty() && (v.back().val >= aux.val)){
                v.pop_back();
            }
            v.push_back(aux);
            if(v.front().poz == i-k){
                v.pop_front();
            }
            if(i >= k){
                S += v.front().val;
            }
        }
    }
    fout<<S<<endl;
    return 0;
}