Pagini recente » Cod sursa (job #2283508) | Cod sursa (job #2595843) | Cod sursa (job #3177766) | Autentificare | Cod sursa (job #384196)
Cod sursa(job #384196)
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define FILE_IN "heavymetal.in"
#define FILE_OUT "heavymetal.out"
const int SIZE=100000;
int n;
struct pConcerte
{
int inc;
int sf;
bool operator > (pConcerte c)
{
return (this->sf > c.sf);
}
bool operator < (pConcerte c)
{
return (this->sf < c.sf);
}
bool operator == (pConcerte c)
{
return (this->sf == c.sf);
}
}v[SIZE];
void merge_sort(int start,int end)
{
if(start==end)
return ;
int mid=start+(end-start)/2;
merge_sort(start,mid);
merge_sort(mid+1,end);
int p1=start;
int p2=mid+1;
int poz_a=0;
pConcerte *a=new pConcerte[end-start+1];
while( (p1<=mid) && (p2<=end) )
{
if( v[p1] < v[p2] )
a[poz_a++]=v[p1++];
else if( v[p2] < v[p1] )
a[poz_a++]=v[p2++];
else if( v[p2]== v[p1] )
{
a[poz_a++]=v[p2++];
a[poz_a++]=v[p1++];
}
}
if(p1<=mid)
for(int i=p1; i<=mid; i++)
a[poz_a++]=v[i];
if(p2<=end)
for(int i=p2; i<=end; i++)
a[poz_a++]=v[i];
poz_a=0;
for(int i=start; i<=end; i++)
v[i]=a[poz_a++];
delete []a;
}
inline int max(int a,int b)
{
return (a>b?a:b);
}
int Lung[165000];
int main()
{
freopen(FILE_IN,"r",stdin);
freopen(FILE_OUT,"w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d %d",&v[i].inc,&v[i].sf);
//merge_sort(1,n);
std::sort(&v[1],&v[n]);
int itr=1;
for(int i=1; i<=v[n].sf; i++)
{
Lung[i]=Lung[i-1];
while(v[itr].sf==i)
{
Lung[i]=max(Lung[i],Lung[v[itr].inc]+v[itr].sf-v[itr].inc);
itr++;
}
}
printf("%d",Lung[v[n].sf]);
return 0;
}