Cod sursa(job #1534382)

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