Cod sursa(job #3126211)

Utilizator TirilaPatricTirila Patric-Gabriel TirilaPatric Data 6 mai 2023 13:02:45
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <deque>
#include <vector>
using namespace std;

int main(){
    ifstream f("deque.in");
    ofstream g("deque.out");
    int N, K;
    int st=0, a, sum=0, i = 0, m = 0;
    f >> N >> K;
    vector<int> Q, V(N+1);
    while(f>>a){
        V[i] = a;
        m+=1;
        while (Q.size()-st>0 && V[i] <= V[Q[Q.size()-1]]){
            Q.pop_back();
        }
        Q.push_back(i);
        while(Q[st]<=i-K){
            st++;
        }
        if (K<=m){
            sum += V[Q[st]];
        }
        i++;
    }
    g << sum;
    f.close();
    g.close();

    return 0;
}