Pagini recente » Cod sursa (job #3263708) | Cod sursa (job #709134) | Cod sursa (job #459021) | Cod sursa (job #735033) | Cod sursa (job #800401)
Cod sursa(job #800401)
#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 ;
}