Pagini recente » Cod sursa (job #2441325) | Cod sursa (job #2833639) | Cod sursa (job #1789935) | Cod sursa (job #893784) | Cod sursa (job #1425550)
#include <fstream>
#include <algorithm>
#define dim 100001
using namespace std;
ifstream fin("procesor.in");
ofstream fout("procesor.out");
long long sum;
int i,j,poz,heap[4*dim],k,n,val[dim],Tmax;
struct cub
{
int x;
int y;
}proces[dim];
int cmp(cub o, cub p)
{
return o.x>p.x;
}
void downDate(int poz)
{
long long po=poz;
while(poz*2<=k)
{
po=poz*2;
if(po+1<=k&&heap[po]<heap[po+1])
po++;
if(heap[poz]<heap[po])
{
swap(heap[po],heap[poz]);
poz=po;
}
else
break;
}
}
void upDate(int poz)
{
while(poz/2>0)
{
if(heap[poz]>heap[poz/2])
{
swap(heap[poz],heap[poz/2]);
poz/=2;
}
else
break;
}
}
int main()
{
fin>>n;
for(i=1;i<=n;i++)
{
fin>>proces[i].x>>val[i];
proces[i].y=i;
if(proces[i].x>Tmax)
Tmax=proces[i].x;
}
sort(proces+1,proces+n+1,cmp);
poz=1;
for(i=Tmax;i>=0;i--)
{
for(j=poz;proces[j].x>i&&j<=n;j++)
{
heap[++k]=val[proces[j].y];
upDate(k);
}
poz=j;
if(k>0)
{
swap(heap[1],heap[k]);
k--;
downDate(1);
}
}
for(i=1;i<=k;i++)
sum+=heap[i];
fout<<sum;
return 0;
}