Cod sursa(job #1577963)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 24 ianuarie 2016 00:35:24
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <deque> /// :(
using namespace std; /// :(
deque <int> d1, d2 ; /// Primul pentru valoare nr. si al doilea pentru pozitia sa

/// 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, "%lld", &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 :(