Cod sursa(job #2131446)

Utilizator mihaicivMihai Vlad mihaiciv Data 14 februarie 2018 18:35:04
Problema Deque Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 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;
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;
    if (fin==st) {
        poz=1;
    }
    else {
        poz++;
    }
}
void rez() {
    st=fin=1;
    v[st]=v[1];
    poz=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<<v[st]<<"\n";
            if (k==poz) {
                st++;
                poz=0;
            }
        }
    }
    g<<Suma;
}
int main() {
    citire();
    rez();
    return 0;
}