Cod sursa(job #1075815)
Utilizator | Data | 9 ianuarie 2014 16:39:11 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.57 kb |
#include <cstdio>
using namespace std;
int i,a[5000003],n,k,b[5000003],j,u,p;
long long Min;
void pune(int i)
{
while(u>=p && a[b[u]]>a[i])
{b[u]=0;--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);
for(i=k;i<=n;++i)
{
pune(i);
Min+=a[b[p]];
if(i-b[p]==k-1) {b[p]=0;p++;}
}
printf("%lld\n",Min);
return 0;
}