Cod sursa(job #1068525)

Utilizator Catalina_BrinzaBrinza Catalina Catalina_Brinza Data 28 decembrie 2013 14:08:31
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#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;
}