Cod sursa(job #371847)

Utilizator mad200647Mihai Toma mad200647 Data 7 decembrie 2009 11:07:27
Problema Deque Scor 100
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],k,n,i,s=0;
int p,u,d[5000001];

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;
}