Cod sursa(job #2732469)

Utilizator AndreeaGeamanuAndreea AndreeaGeamanu Data 28 martie 2021 23:11:07
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[5000010], aux[5000010]={-1};

int main()
{   int n,k,s=0,i,j=-1,poz=0;
    in>>n>>k;
    for(i=0; i<n; i++){
        in>>v[i];
        if(j!=-1){
        if(aux[j]!=-1)
            while(poz<=j && v[i]<=v[aux[j]]){
                aux[j]=-1;
                j--;
            }
        }
        j++;
        aux[j]=i;
        if(i>=k-1){
            s=s+v[aux[poz]];
        }
        if(i-aux[poz]>=k-1) poz++;
    }
    out<<s;
    in.close();
    out.close();
    return 0;
}