Cod sursa(job #1577961)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 24 ianuarie 2016 00:31:45
Problema Deque Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <deque> /// :(
using namespace std; /// :(
deque <int> d1, d2 ; /// :(

/// Cu toate aceste nu moare nimeni daca apare exstensia C++
int main()
{
    FILE *fin, *fout ;
    fin = fopen ("deque.in", "r" ) ;
    fout = fopen ("deque.out", "w" ) ;
    long long n, i, s, x, k ;
    fscanf (fin, "%lld%lld", &n, &k ) ;
    s = 0 ;
    for (i = 1 ; i <= n ; i++ ) {
      fscanf (fin, "%d", &x) ; /// Citim elementul
      if (d1.empty() != 1 && i-d2.front() >= k ) { /// Daca am trecut de o secventa
       d1.pop_front() ;
       d2.pop_front() ; /// Trecem la una noua
      }
      while (d1.empty() != 1 && d1.back() >= x ) { /// Daca elementul nostru este mai mic ca ultimele din deque
        d1.pop_back() ; /// Le taie  :)
        d2.pop_back() ;
      }
    d1.push_back(x) ; /// Adaugam elementul
    d2.push_back(i) ;
    if (i >= k )
      s+= d1.front() ;///Marima suma cu minimul
    }
    fprintf (fout, "%lld", s ) ; /// Afisam suma
    return 0;
}


/// Imi pare rau Cristian Francu :(