Pagini recente » Cod sursa (job #2080452) | Cod sursa (job #77537) | Cod sursa (job #941159) | Cod sursa (job #3169244) | Cod sursa (job #1534382)
#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;
}