Cod sursa(job #866459)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 28 ianuarie 2013 08:36:30
Problema Heapuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int NMAX = 1000005;
int n,i,t,p,TMAX,N,A[NMAX];
long long sum;
vector<int> H[NMAX];
vector<int>::iterator it;
void heapup(int F)
{
    int P=F/2;
    if(!P) return;
    if(A[F]>A[P])
    {
        swap(A[F],A[P]);
        heapup(P);
    }
}
void heapdown(int P)
{
    int F=2*P;
    if(F>N) return;
    if(F+1<=N && A[F+1]>A[F]) F=F+1;
    if(A[F]>A[P])
    {
        swap(A[F],A[P]);
        heapdown(F);
    }
}
int main()
{
    freopen("procesor.in","r",stdin);
    freopen("procesor.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&t,&p);
        H[t].push_back(p);
        TMAX=max(TMAX,t);
    }
    for(i=TMAX;i;i--)
    {
        if(!H[i].empty())
        {
            for(it=H[i].begin();it!=H[i].end();it++)
                A[++N]=*it,heapup(N);
        }
        if(N)
        {
            A[1]=A[N];
            heapdown(1);
            N--;
        }
    }
    for(i=1;i<=N;i++) sum+=A[i];
    printf("%lld\n",sum);
    return 0;
}