Cod sursa(job #1976581)

Utilizator Coroian_DavidCoroian David Coroian_David Data 3 mai 2017 19:51:43
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

FILE *f, *g;

int n, mx, l;

int h[100009];

int nod;

struct oaia
{
    int d, c;
};

oaia v[100009];

void readFile()
{
    f = fopen("lupu.in", "r");

    fscanf(f, "%d%d%d", &n, &mx, &l);

    int i, a, b;
    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%d%d", &v[i].d, &v[i].c);
    }

    fclose(f);
}

bool cmp(oaia a, oaia b)
{
    return a.d > b.d;
}

void ins(int i, int nr)
{
    nod ++;

    h[nod] = i;

}

void sch(int &a, int &b)
{
    int aux = a;
    a = b;
    b = aux;
}

void downHeap(int poz)
{
    int fiu = poz;

    while(poz * 2 <= nod)
    {
        fiu = poz;

        if(poz * 2 <= nod && h[poz * 2] < h[fiu])
            fiu = poz * 2;

        if(poz * 2 + 1 <= nod && h[poz * 2 + 1] < h[fiu])
            fiu = poz * 2 + 1;

        if(fiu != poz)
        {
            sch(h[fiu], h[poz]);

            poz = fiu;
        }
    }
}

void upHeap(int poz)
{
    while(poz > 1 && h[poz] < h[poz / 2])
    {
        //printf("%d %d %d\n", poz, h[poz], h[poz / 2]);

        sch(h[poz], h[poz / 2]);

        poz /= 2;
    }
}

void del()
{
    h[1] = 0;

    sch(h[1], h[nod]);

    nod --;

    downHeap(1);
}

void ins(int poz)
{
    nod ++;

    h[nod] = poz;

    upHeap(nod);
}

long long rez;

void solve()
{
    sort(v + 1, v + n + 1, cmp);

    int i = 1;
    while(i <= n && v[i].d > mx)
        i ++;

    for(; i <= n; i ++)
    {
       // printf("Suntem pe %d %d %d", i, v[i].d, v[i].c);

        if(v[i].d <= mx)
        {
               // printf("****");
            ins(v[i].c);

            rez += v[i].c;

            mx -= l;
        }

        else
        {
            if(nod > 0 && v[i].c > h[1])
            {
               // printf("*");
                rez -= h[1];
                rez += v[i].c;

                del();
                ins(v[i].c);
            }
        }
       // printf("\n");

       // printf("  %d\n", h[1]);
       // printf("%d   %d\n\n", h[2], h[3]);
    //    printf("%d  ")
    }
}

void printFile()
{
    g = fopen("lupu.out", "w");

    fprintf(g, "%lld\n", rez);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}