Cod sursa(job #2971952)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 28 ianuarie 2023 13:41:59
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.48 kb
#include<bits/stdc++.h>
#define DIM 5000001
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
deque <int> d;
long long v[DIM];
long long n, i, k, sp;
int main(){
fin >> n >> k;
for(i=1;i<=n;i++)
    fin >> v[i];
for(i=1;i<=n;i++){
    while(!d.empty() && v[d.back()] > v[i])
        d.pop_back();
    d.push_back(i);
    if(i >= k)
    while(i - d.front() >= k)
        d.pop_front();
    if(i >= k)
        sp += v[d.front()];
}
fout << sp;
}