Cod sursa(job #1534383)

Utilizator DiClauDan Claudiu DiClau Data 23 noiembrie 2015 18:23:42
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N = 100005;
struct ptSortare
{
    int d, c;
};
ptSortare a[N];
int h[N], v[N], m;
bool cmp (ptSortare a, ptSortare b)
{
    if (a.d > b.d)
        return true;
    if (a.d < b.d)
        return false;
    if (a.c > b.c)
        return true;
    return false;
}
void schimba (int p1, int p2)
{
    int aux = h[p1];
    h[p1] = h[p2];
    h[p2] = aux;
}
void urca (int p)
{
    while (p > 1 && v[h[p]] < v[h[p / 2]])
    {
        schimba (p, p / 2);
        p /= 2;
    }
}
void coboara (int p)
{
    int fS = p * 2 + 1, fD = p * 2, bun = p;
    if (fS <= m && v[h[fS]] < v[h[bun]])
        bun = fS;
    if (fD <= m && v[h[fD]] < v[h[bun]])
        bun = fD;
    if (bun != p)
    {
        schimba (bun, p);
        coboara (bun);
    }
}
int main ()
{
    FILE *in, *out;
    in = fopen ("lupu.in", "r");
    out = fopen ("lupu.out", "w");
    int n, x, l;
    fscanf (in, "%d%d%d", &n, &x, &l);
    int i;
    for (i = 1; i <= n; i++)
        fscanf (in, "%d%d", &a[i].d, &a[i].c);
    sort (a + 1, a + n + 1, cmp);
    int c = 1;
    while (a[c].d > x)
        c++;
    int fuga = 0;
    for (i = c; i <= n; i++)
    {
        if (a[i].d  + fuga <= x)
        {
            v[++m] = a[i].c;
            h[m] = m;
            urca (m);
            fuga += l;
        }
        else
        {
            if (a[i].c > v[h[1]])
            {
                v[h[1]] = a[i].c;
                coboara (1);
            }
        }
    }
    long long s = 0;
    for (i = 1; i <= m; i++)
        s += (long long) v[h[i]];
    fprintf (out, "%lld", s);
    return 0;
}