Pagini recente » Cod sursa (job #2744573) | Cod sursa (job #2228140) | Cod sursa (job #1238174) | Cod sursa (job #2807036) | Cod sursa (job #825235)
Cod sursa(job #825235)
#include <fstream>
#define NMAX 5000004
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
struct pct{int poz, val;}V[NMAX];
int N,T,P,K;
void Heap_Up(int p)
{
if(p>1&&V[p/2].val>V[p].val)
{
pct aux = V[p/2];
V[p/2] = V[p];
V[p] = aux;
Heap_Up(p/2);
}
}
void Heap_Down(int p)
{
int min = p;
if(V[min].val>V[2*p].val&&2*p<=N)
min = 2*p;
if(V[min].val>V[2*p+1].val&&2*p+1<=N)
min = 2*p+1;
if(min != p)
{
pct aux = V[min];
V[min] = V[p];
V[p] = aux;
}
}
void Push_Heap(pct x)
{
V[++N] = x;
Heap_Up(N);
}
void Pop_Heap()
{
while(V[1].poz+K-1<=P)
V[1] = V[N--],Heap_Down(1);
}
int main()
{
int Sum = 0;
pct t;
in>>T>>K;
for(P=1;P<=T;P++)
{
in>>t.val;
t.poz = P;
Push_Heap(t);
if(P>=K)
Sum+=V[1].val,Pop_Heap();
}
out<<Sum<<'\n';
return 0;
}