Pagini recente » Cod sursa (job #1068467) | Cod sursa (job #1741816) | Istoria paginii utilizator/dope_guy | Cod sursa (job #998208) | Cod sursa (job #1068525)
#include<fstream>
#include<algorithm>
#define mi -10000001
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
struct strut{
int a,b;
};
int n,k,i,j,l,fi,nr=0,s=0,x;
strut h[5000001];
int fin(int x,int y)
{
if(h[x].a<h[y].a)
return x;
return y;
}
int main()
{
f>>n>>k;
h[0].a=mi;
for(i=1;i<=k;i++)
{
f>>x;
h[i].a=x;
h[i].b=i;
j=i;
while(h[j].a<h[j/2].a)
{
swap(h[j],h[j/2]);
j/=2;
}
}
s=h[1].a;
nr=k;
for(i=k+1;i<=n;i++)
{
nr++;
f>>x;
h[nr].a=x;
h[nr].a=i;
j=nr;
while(h[j].a<h[j/2].a)
{
swap(h[j],h[j/2]);
j/=2;
}
while(!(h[1].a>=i-k+1&&h[1].a<=i))
{
swap(h[1],h[nr]);
nr--;
int j=1;
while(2*j+1<=nr)
{
l=fin(2*j,2*j+1);
if(!(h[j].a>h[l].a))
break;
swap(h[j],h[l]);
j=l;
}
if(2*j+1>nr && 2*j==nr && h[j].a>h[2*j].a)
swap(h[j],h[2*j]);
}
s+=h[1].a;
}
g<<s;
f.close();g.close();
return 0;
}