Cod sursa(job #1779515)

Utilizator dragomir_ioanDragomir Ioan dragomir_ioan Data 15 octombrie 2016 13:32:19
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<cstdio>
#include<deque>
using namespace std;

int main() {
    FILE *fin = fopen("deque.in", "r"),
        *fout = fopen("deque.out", "w");

    int n, k;
    long long suma = 0;
    fscanf(fin, "%d%d", &n, &k);

    deque<int> nr, poz;

    for(int i=1; i<=n; i++) {
        int x;
        fscanf(fin, "%d", &x);
        while(!nr.empty() && nr.back() > x)
            nr.pop_back(), poz.pop_back();
        nr.push_back(x);
        poz.push_back(i);

        if(i>=k) {  // daca nu e inca in construire prima secventa
            while(poz.back() - poz.front() >= k)
                nr.pop_front(), poz.pop_front();
            suma += nr.front();
        }
    }

    fprintf(fout, "%lld\n", suma);

    return 0;
}