Cod sursa(job #1303334)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 27 decembrie 2014 21:03:59
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
#define nmax 150005
using namespace std;
ifstream f("lupu.in");
FILE *g=fopen("lupu.out","w");
int n,x,l;
long long sol;
struct oaie {int d;int p;};
oaie v[nmax];

int heap[nmax],k;

void urca(int C)
{int P=C/2;
while (P>0)
    {if (heap[C]>heap[P]) {
                swap(heap[C],heap[P]);
                C=P;
                P/=2;}
         else break;
}
}
void coboara(int P)
{int C;
C=P*2;
while (C<=k) {
    if (C+1<=k&&heap[C+1]>heap[C]) C=C+1;
    if (heap[P]<heap[C])
            {swap(heap[P],heap[C]);
             P=C;
             C=C*2;
             }
        else break;
}


}


bool cmp(const oaie &a,const oaie &b)
{return a.d>b.d;}

int main(){

    int i,j;
    f>>n>>x>>l;
    for (i=1;i<=n;i++)
            {v[i].d/=l;
             if (v[i].d>x) {i--;n--;}
                    else {
                        f>>v[i].d>>v[i].p;
                        v[i].d=x-v[i].d;
                        v[i].d/=l;
                        v[i].d++;
                    }
            }
    sort(v+1,v+n+1,cmp);
    j=v[1].d;
    i=1;
    while (j>=1)
            {while (v[i].d>=j) {heap[++k]=v[i].p;
                                urca(k);
                                i++;}
             sol+=1LL*heap[1];
             heap[1]=heap[k];
             heap[k]=0;
             k--;
             coboara(1);
             j--;
             }
    fprintf(g,"%lld",sol);
return 0;
}