Pagini recente » Cod sursa (job #2894863) | Cod sursa (job #360501) | Cod sursa (job #261157) | Cod sursa (job #1632251) | Cod sursa (job #800395)
Cod sursa(job #800395)
#include<cstdio>
#define ll long long
ll n , k , *a , sol =0 , *dq, l=0 , lfront=1 ;
int main()
{
freopen( "deque.in", "r",stdin );
freopen( "deque.out" ,"w", stdout );
scanf("%d %d" , &n, &k);
a=new ll [n+3];
dq=new ll[ n +3 ];
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
}
for(int i = 1 ; i <=n ; ++i)
{
while ( ( l>=lfront ) >= 1 && a[ dq [ l ] ] >= a [ i] ) --l;
dq[ ++l ]= i;
while ( dq[ lfront ] <= i-k ) ++lfront ;
if( i >= k )sol += a[dq[ lfront ] ] ;
}
printf ( "%lld\n" ,sol ) ;
return 0 ;
}