Cod sursa(job #2731193)

Utilizator SofeiAndreiSofei Andrei SofeiAndrei Data 27 martie 2021 14:52:18
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k,i,primul,ultimul;
bool OK;
long long S;
int x[5000001],Deque[5000001];
int main()
{
    f>>n>>k;
    for(i=1;i<=n;i++){
        f>>x[i];
    }
    S=0;
    primul=1;
    ultimul=0;
    for(i=1;i<=n;i++){
        while(x[i]<x[Deque[ultimul]]){
            if(primul>ultimul){
                break;
            }
            else{
                ultimul--;
            }
        }
        ultimul++;
        Deque[ultimul]=i;
        if(Deque[primul]==i-k){
            if(OK==0){
                S=x[Deque[primul]];
                //am descoperit prima secventa de lungima k
                OK=1;
            }
            //am ajuns la o secventa de lungime k, asa ca nu mai avem nevoie de primul
            primul++;
        }
        if(OK==1){
            S=S+x[Deque[primul]];
        }
    }
    g<<S;
    return 0;
}