Cod sursa(job #2131426)

Utilizator mihaicivMihai Vlad mihaiciv Data 14 februarie 2018 18:24:24
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#define nmax 5000001
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
long long int k,n,v[nmax],st,fin,poz[nmax];
void citire() {
    f>>n>>k;
    for (int i=1;i<=n;i++) {
        f>>v[i];
    }
}
void Adauga(long long int val,long long int pos) {
    while (st<=fin && val<v[fin]) {
        fin--;
    }
    fin++;
    v[fin]=val;
    poz[fin]=pos;

}
void rez() {
    st=fin=1;
    v[st]=v[1];
    poz[st]=1;
    long long int Suma=0;
    for (int i=2;i<=n;i++) {
        Adauga(v[i],i);
        if (i>=k) {
            Suma=Suma+v[st];
            //cout<<d[st]<<"\n";
            if (i+1-k>=poz[st]) {
                st++;
            }
        }
    }
    g<<Suma;
}
int main() {
    citire();
    rez();
    return 0;
}