Pagini recente » Cod sursa (job #946371) | Cod sursa (job #1216507) | Cod sursa (job #3287252) | Cod sursa (job #2144031) | Cod sursa (job #1066473)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("deque.in");
ofstream out ("deque.out");
struct structura
{
int valoare;
int pozitie;
};
void swap (structura &a, structura &b)
{
structura t=a;
a=b;
b=t;
}
int minim (structura a, structura b, int i)
{
if (a.valoare>b.valoare)
return 2*i+1;
else
return 2*i;
}
void up(structura *v, int i)
{
while (i!=1 && v[i].valoare<v[i/2].valoare)
{
swap (v[i], v[i/2]);
i=i/2;
}
}
void push (structura *v, int poz, structura val)
{
v[poz]=val;
up(v, poz);
}
void down(structura *v, int i, int N)
{
if (2*i>N)
return;
else
{
if (2*i+1<=N)
{
int poz=minim(v[2*i], v[2*i+1], i);
if (v[poz].valoare>=v[i].valoare)
return;
else
{
swap (v[i], v[poz]);
down (v, poz, N);
}
}
else
{
if (v[2*i].valoare>=v[i].valoare)
return;
else
{
swap (v[i], v[2*i]);
return;
}
}
}
}
void pop (structura *v, int N)
{
v[1]=v[N];
down(v, 1, N);
}
int main()
{
int N;
structura v[260258], aux;
int K;
in>>N>>K;
long long int suma=0;
int lungime_heap=0;
for (int i=1;i<K;++i)
{
in>>aux.valoare;
aux.pozitie=i;
push(v, i, aux);
++lungime_heap;
}
for (int i=K;i<=N;++i)
{
in>>aux.valoare;
aux.pozitie=i;
push(v, i, aux);
++lungime_heap;
while (i-v[1].pozitie>=K)
{
pop(v, lungime_heap);
}
suma+=v[1].valoare;
}
out<<suma;
return 0;
}