Cod sursa(job #1425550)

Utilizator GinguIonutGinguIonut GinguIonut Data 27 aprilie 2015 17:25:56
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#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;
}