Pagini recente » Cod sursa (job #489287) | Cod sursa (job #638241) | Cod sursa (job #1200991) | Cod sursa (job #1322059) | Cod sursa (job #468110)
Cod sursa(job #468110)
#include<cstdio>
const int N = 5000001;
int a[N],dq[N];
int st=1 , dr=0 , s=0 , k;
inline void stanga(int i)
{
if ( i-dq[st] == k ) ++st;
}
void dreapta(int i)
{
while (st<=dr && a[dq[dr]]>=a[i] )
--dr;
dq[++dr] = i;
}
int main()
{
freopen ("deque.in" , "r" , stdin );
freopen ("deque.out", "w" , stdout);
int n,i;
scanf("%d %d",&n,&k);
for (i=1 ; i<=n ; ++i )
{
scanf ("%d" , &a[i] );
if(i>k)
stanga(i);
dreapta(i);
if(i>=k)
s+=a[dq[st]];
}
printf( "%d\n" , s ) ;
return 0;
}