Cod sursa(job #1075789)
Utilizator | Alexa Tudose Alexa2001 | Data | 9 ianuarie 2014 16:17:25 |
---|---|---|---|
Problema | Deque | Scor | 25 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <cstdio>
using namespace std;
int i,a[5000003],n,k,b[5000003],Min,j,u,p;
void pune(int i)
{
while(u>=p && a[b[u]]>a[i])
--u;
++u;
b[u]=i;
}
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d %d\n",&n,&k);
for(i=1;i<=n;++i)
scanf("%d",&a[i]);
p=1;u=0;
for(i=1;i<k;++i)
pune(i);
Min=0;
for(i=k;i<=n;++i)
{
pune(i);
Min+=a[b[p]];
if(i-b[p]==k-1) p++;
}
printf("%d\n",Min);
return 0;
}