Cod sursa(job #1976575)

Utilizator Coroian_DavidCoroian David Coroian_David Data 3 mai 2017 19:36:21
Problema Lupul Urias si Rau Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.58 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)
{
    if(a.d < b.d)
        return 0;

    if(a.d > b.d)
        return 1;

    return a.c > b.c;
}

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

    h[nod] = i;

}

void sch(int a, int b)
{
    int aux = h[a];
    h[a] = h[b];
    h[b] = aux;
}

void downHeap(int poz)
{
    int mn, pozf;
    while(poz * 2 <= nod)
    {
        mn = v[h[poz]].c;
        pozf = -1;

        if(poz * 2 <= nod)
        {
            if(v[h[poz * 2]].c < mn)
            {
                mn = v[h[poz * 2]].c;

                pozf = 0;
            }
        }

        if(poz * 2 + 1 <= nod)
        {
            if(v[h[poz * 2 + 1]].c < mn)
            {
                mn = v[h[poz * 2]].c;

                pozf = 1;
            }
        }

        if(pozf == -1)
            return;

        sch(poz, poz * 2 + pozf);

        poz = poz * 2 + pozf;
    }
}

void upHeap(int poz)
{
    while(poz > 1)
    {
        if(v[h[poz / 2]].c > v[h[poz]].c)
        {
            sch(h[poz / 2], h[poz]);

            poz /= 2;
        }

        else
            return;
    }
}

void del()
{
    sch(h[1], h[nod]);

    nod --;

    downHeap(1);
}

void ins(int poz)
{
    nod ++;

    h[nod] = poz;

    upHeap(nod);
}

int rez[100009];

void aduna(int a[], int nr)
{
    int t = nr;
    int i;
    for(i = 1; i <= a[0] || t; i ++)
    {
        t += a[i];

        a[i] = t % 10;

        t /= 10;
    }

    a[0] = i - 1;
}

void scd(int a[], int b[])
{
    int i;
    int t = 0;
    for(i = 1; i <= a[0] || t; i ++)
    {
        a[i] -= b[i];
        a[i] -= t;

        t = 0;

        if(a[i] < 0)
            a[i] += 10, t = 1;
    }

    while(a[0] > 0 && a[a[0]] == 0)
        a[0] --;
}

void toV(int a[], int nr)
{
    a[0] = 0;

    memset(a, 0, sizeof(a));

    while(nr != 0)
    {
        a[++ a[0]] = nr % 10;

        nr /= 10;
    }
}

int c[10009];

void scade(int a[], int nr)
{
    toV(c, nr);

    scd(a, c);
}

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\n", i, v[i].d, v[i].c);

        if(v[i].d <= mx)
        {
            ins(i, v[i].c);

           // printf("Introducem pe %d, %d\n",i, v[i].c);

            aduna(rez, v[i].c);

            mx -= l;
        }

        else
        {
           // printf("++Comparam %d cu %d\n", v[h[1]].c, v[i].c);

            if(v[i].c > v[h[1]].c)
            {
                aduna(rez, v[i].c);
                scade(rez, v[h[1]].c);


           // printf("Introducem pe %d, %d\n",i, v[i].c);
           // printf("SCoatem pe %d, %d\n", h[1], v[h[1]].c);

                del();
                ins(i, v[i].c);
            }
        }
    }
}

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

    int i;
    for(i = rez[0]; i >= 1; i --)
        fprintf(g, "%d", rez[i]);

    fprintf(g, "\n");

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}