Cod sursa(job #800401)

Utilizator MtkMarianHagrSnaf MtkMarian Data 21 octombrie 2012 15:49:13
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<cstdio>
#include<deque>
using namespace std ;



deque < int > dq ;

int  n , k , *a ;
long long sol =0 ;

int main()
{
	freopen( "deque.in", "r",stdin );
	freopen( "deque.out" ,"w", stdout ); 

	scanf("%d %d" , &n, &k);
	a=new int [n+3];
	for(int i=1;i<=n;++i) 
	{
		scanf("%d",&a[i]);
	}




	for(int i = 1 ; i <=n ; ++i)
	{
	
			
			
			while ( dq.size() && a [ dq.back() ] >= a [ i ] ) dq.pop_back( ) ;			
			
			dq.push_back ( i );


			while ( dq.front () <= i-k ) dq.pop_front () ;
		
	
			if( i >= k  ) sol  +=  a [dq[ 0 ] ] ;
			
	}

	

	printf ( "%lld\n " ,sol  ) ;
	return 0 ;
}