Pagini recente » Rating Ursu Catalin Eugen (UrsuCE) | Diferente pentru home intre reviziile 758 si 759 | Cod sursa (job #1044590) | Cod sursa (job #748979) | Cod sursa (job #2547576)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("procesor.in");
ofstream out("procesor.out");
const int dim = 100005;
int n;
pair <int,int> v[dim];
int heap[dim],len;
void Schimba(int p,int q)
{
swap(heap[p] , heap[q]);
}
void Urca(int p)
{
while (p > 1 && heap[p/2] < heap[p])
{
Schimba(p,p/2);
p /= 2;
}
}
void Coboara(int p)
{
int bun = p,fs = 2*p,fd = 2*p+1;
if (fs <= len && heap[fs] > heap[bun])
{
bun = fs;
}
if (fd <= len && heap[fd] > heap[bun])
{
bun = fd;
}
if (bun != p)
{
Schimba(p,bun);
Coboara(bun);
}
}
void Adauga(int nr)
{
heap[++len] = nr;
Urca(len);
}
void Sterge()
{
Schimba(1, len--);
Coboara(1);
}
int main()
{
in >> n;
for (int i=1; i<=n; i++)
{
in >> v[i].first >> v[i].second;
}
sort(v+1,v+n+1);
int j = n;
for (int i=v[n].first; i>=1; i--)
{
while (j >= 1 && v[j].first >= i)
{
Adauga(v[j].second);
j--;
}
if (len >= 1)
Sterge();
}
long long int s = 0;
while (len >= 1)
{
s += heap[1];
Sterge();
}
out << s;
return 0;
}