Pagini recente » Cod sursa (job #2980718) | Cod sursa (job #2350753)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int N=100005;
struct spectacol
{
int st,fin;
};
spectacol a[N];
int n,d[N];
bool cmp(spectacol A,spectacol B)
{
if(A.fin==B.fin)
return A.st<B.st;
return A.fin<B.fin;
}
int cautbin(int inceput,int dr)
{
int st=1,mid;
while(st<=dr)
{
mid=(st+dr)/2;
if(a[mid].fin<=inceput)
{
st=mid+1;
}
else
dr=mid-1;
}
return dr;
}
int main()
{
int i,j;
in>>n;
for(i=1; i<=n; i++)
in>>a[i].st>>a[i].fin;
sort(a+1,a+n+1,cmp);
d[1]=a[1].fin-a[1].st;
for(i=2; i<=n; i++)
{
j=cautbin(a[i].st,i-1);
//caut cel mai bun j astfel incat A[i].st>=A[j].fin
d[i]=max(d[i-1],d[j]+a[i].fin-a[i].st);
}
out<<d[n];
return 0;
}