Cod sursa(job #1576761)

Utilizator ruxi.icleanuRuxandra Icleanu ruxi.icleanu Data 22 ianuarie 2016 20:11:30
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <stdlib.h>
#include <deque>

using namespace std;

deque <int> val, poz;

int main()
{
    int n, k, i, x;
    long long s;
    FILE *fi, *fo;
    fi = fopen("deque.in", "r");
    fo = fopen("deque.out", "w");
    fscanf(fi, "%d%d", &n, &k);
    s=0;
    for(i=1; i<=n; i++) {
        fscanf(fi, "%d", &x);
        if(val.empty()!=1 && i-poz.front()>=k) {
            val.pop_front();
            poz.pop_front();
        }
        while(val.empty()!=1 && x<=val.back()) {
            val.pop_back();
            poz.pop_back();
        }
        val.push_back(x);
        poz.push_back(i);

        if(i>=k)
            s+=val.front();
    }
    fprintf(fo, "%lld", s);
    fclose(fi);
    fclose(fo);
    return 0;
}