Cod sursa(job #632991)

Utilizator JohannesJohannes Dragulanescu Johannes Data 12 noiembrie 2011 16:58:14
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <deque>
#include <stdio.h>
using namespace std;

deque <int> dque, position;
int n,k; // lungimea sirului respectiv subsecventei

int main ()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
    
	int element;
    long long suma = 0; 

	scanf("%d%d",&n,&k);
        
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&element);

		while (!dque.empty() && element <= dque.back()) 
		{
			// Cat timp elementul curent este mai mic decat ultimul element din deque, eliminam ultimul element din deque
			dque.pop_back(); 
			position.pop_back();
		}

		dque.push_back(element);

		// Adaugam pozitia elementului curent in deque
		position.push_back(i);

		if (position.front() <= i-k)
		{
			dque.pop_front();
			position.pop_front();
		}
		 
		// Afisam minimul, acesta aflandu-se in varful deque-ului
		if (i >= k) suma += dque.front();    
		
    }
    
	printf("%d",suma);

    return 0;
}