Cod sursa(job #935454)

Utilizator rudarelLup Ionut rudarel Data 3 aprilie 2013 15:00:44
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#define input "lupu.in"
#define output "lupu.out"
#define nmax 200002
struct oaie {long long d,c,t;} o[nmax],aux,s1[nmax],s2[nmax],vect[nmax];
long long n,x,l,sol,l1,l2,j,i1,i2,nl,pc,t,timp,nm;
void citire()
{
    long i;
    FILE *fin;
    fin=fopen(input,"r");
    fscanf(fin,"%lld %lld %lld",&n,&x,&l); nm=0;
    for (i=1;i<=n;i++)      
        {
         nm++;
         fscanf(fin,"%lld %lld",&o[nm].d,&o[nm].c);    
         o[nm].t=1+(x-o[nm].d)/l;
         if (o[nm].d>x) nm--;
        }
    fclose(fin);
}
void afisare()
{
    FILE *fout;
    fout=fopen(output,"w");
    fprintf(fout,"%lld",sol);
    fclose(fout);
}
void merge(long ls, long ld)
{
    if (ls<ld)
        {
         long k=(ls+ld)/2,kk;
         merge(ls,k);
         merge(k+1,ld);
         l1=0;
         l2=0;
         for (j=ls;j<=k;j++) s1[++l1]=o[j];
         for (j=k+1;j<=ld;j++) s2[++l2]=o[j];
         i1=1;
         i2=1;
         k=ls-1;
         while (i1<=l1&&i2<=l2)
             if (s1[i1].t<s2[i2].t) o[++k]=s2[i2++];
                else o[++k]=s1[i1++];
         for (kk=i1;kk<=l1;kk++) o[++k]=s1[kk];
         for (kk=i2;kk<=l2;kk++) o[++k]=s2[kk];
        }
}
void urca(long x)
{
    if (vect[x].c>vect[x/2].c&&x>1)
       {
        aux=vect[x];
        vect[x]=vect[x/2];
        vect[x/2]=aux;
        urca(x/2);
       }   
}
void adauga()
{
    vect[++nl]=o[pc];
    urca(nl);
}
void scoatecap(long k)
{
    if (((vect[2*k].c)||(vect[2*k+1].c))&&(k<=nl))
        if (vect[2*k+1].c>vect[2*k].c)
            {
            aux=vect[k];
            vect[k]=vect[2*k+1];
            vect[2*k+1]=aux;
            scoatecap(2*k+1);
            }  
        else
            {
            aux=vect[k];
            vect[k]=vect[2*k];
            vect[2*k]=aux;
            scoatecap(2*k);
            }  
}
void solve()
{
    merge(1,n);
    nl=0;
    timp=o[1].t; pc=1; sol=0;
    while (timp)
          {
            while (o[pc].t==timp) {adauga(); pc++;}
            sol+=vect[1].c;
            vect[1].c=0;
            scoatecap(1);
            timp--;
          }        
}
int main()
{
    citire();
    solve();
    afisare();
    return 0;
}