Cod sursa(job #331400)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 13 iulie 2009 21:29:30
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

int n,x,l,k,maxi,j,i,imax,rez;

struct nod
{
       int d,puf,fol;
}a[100100];

bool comp(nod x,nod y)
{ 
     if(x.d!=y.d) return x.d<y.d;
     else return x.puf<y.puf;
} 

int cautbin(int x)
{ 
    int st=1,dr=n,mij;
    while(st<=dr) { mij=(st+dr)/2;
                    if((a[mij].d+k<=x&&a[mij+1].d+k>x)||(a[mij].d+k<=x&&mij+1==n)) return mij;
                    else if(a[mij].d+k<=x&&a[mij+1].d+k<=x) st=mij+1;
                    else dr=mij-1;
                  }
    return 0;
}                 

int main()
{ 
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    
    scanf("%d %d %d",&n,&x,&l);
    for(i=1;i<=n;i++) scanf("%d %d",&a[i].d,&a[i].puf);
    
    sort(a+1,a+n+1,comp);
   while(x>=a[1].d+k) 
                      { i=cautbin(x);    
                         while(a[i].fol) --i;     
                         j=i; 
                         maxi=0;
                         imax=0;
                         while(a[j].d+k<=x&&a[j].d+k+l>x&&j>0) { if(a[j].puf>maxi) { maxi=a[j].puf; 
                                                                                     imax=j;
                                                                                   }    
                                                                  j--;
                                                               }                     
                         if(!maxi) { maxi=a[i].puf;
                                     a[i].fol=1;
                                   }
                         else a[imax].fol=1;
                         rez+=maxi;
                         k+=l;
                      }
   printf("%d\n",rez);
   fclose(stdin);
   fclose(stdout);
   return 0;
}