Cod sursa(job #786567)

Utilizator legionarulCorneliu Zelea Codreanu legionarul Data 11 septembrie 2012 16:43:40
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
 # include <fstream>
 # include <cstring>
 # include <algorithm>
 # include <vector>
 # include <deque>
 
 # define dim 5000005
 
 using namespace std;
 
 ifstream f("deque.in");
 ofstream g("deque.out");
 
 int a[ dim ];
 
 deque < int > q;
 
 int n, k;
 
 long long sol;
 
 void citire()
 {
	 int i;
	 
	 f >> n >> k;
	 for ( i = 1 ; i <= n ; i++ )
		 f >> a[ i ];
 }
 
 void rezolva()
 {
	 int i;
	 
	 q.push_front( 1 );
	 
	 for ( i = 2 ; i <= n ; i++ )
	 {
		 while ( a[ q.back() ] >= a[ i ] && q.size() != 0 )
			 q.pop_back();
		 
		 q.push_back( i );
		 
		 if ( q.front()  == i - k )
			 q.pop_front();
		 
		 if ( i >= k )
			 sol = sol + a[ q.front() ];
	 }
	 
	 g << sol;
 }
 
 
 
 int main()
 {
	 citire();
	 rezolva();
	 return 0;
 }