Cod sursa(job #1779479)

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

#define DEBUG false
#define DBG if(DEBUG)

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

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

    deque<int> nr, poz;

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

DBG     printf("nr  %d %d %d %d %d\n", nr[0], nr[1], nr[2], nr[3], nr[4]);
DBG     printf("poz %d %d %d %d %d\n", poz[0], poz[1], poz[2], poz[3], poz[4]);

        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, "%d\n", suma);

    return 0;
}