Pagini recente » Cod sursa (job #362752) | Cod sursa (job #157602) | Cod sursa (job #1091430) | Cod sursa (job #1874793) | Cod sursa (job #1577963)
#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 :(