Cod sursa(job #371845)

Utilizator spidyvenomMarius Toma spidyvenom Data 7 decembrie 2009 11:01:50
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.35 kb
Raporteaza aceasta sursa 
#include<fstream.h>
ifstream f("deque.in");
ofstream g("deque.out");
long long v[5000001],d[5000001],p,u,k,n,i,s=0;

void deque()
{
p=1;u=0;
for(i=1;i<=n;i++)
	{
	while(p<=u && v[i]<=v[d[u]])u--;
	d[++u]=i;
	if(d[p]+k<=i)p++;
	if(i>=k)s+=v[d[p]];
	}
}

int main()
{
f>>n>>k;
for(i=1;i<=n;i++)
	f>>v[i];
deque();
g<<s;
return 0;
}