Pagini recente » Cod sursa (job #2605284) | Cod sursa (job #536357) | Cod sursa (job #3134899) | Cod sursa (job #621557) | Cod sursa (job #520377)
Cod sursa(job #520377)
#include<fstream>
#include<algorithm>
using namespace std;
int n,best[100020], p[100020];
struct intervale{
int x,y;};
intervale v[100020];
int comp(int i, int j)
{
if(v[i].y<v[j].y)
return 1;
return 0;
}
int maxim(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int rez;
void cautare(int st,int dr,int val);
int main()
{
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
fin>>n;
int i;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y, p[i]=i;
sort(p+1,p+n+1,comp);
best[1]=v[p[1]].y-v[p[1]].x;
for(i=2;i<=n;i++)
{
rez=0;
cautare(1,i-1,v[p[i]].x);
int sol=rez;
best[i]=maxim(best[i-1],best[sol]+v[p[i]].y-v[p[i]].x);
}
fout<<best[n];
return 0;
}
void cautare(int st,int dr,int val)
{
if(st==dr)
{
if(v[p[st]].y<=val && st>rez)
rez=st;
return ;
}
else
{
int mijloc=(st+dr)/2;
if(v[p[mijloc]].y<=val)
{
if(mijloc>rez)
rez=mijloc;
cautare(mijloc+1,dr,val);
}
else
cautare(st,mijloc,val);
}
}