Pagini recente » Cod sursa (job #294714) | Cod sursa (job #1444176) | Cod sursa (job #1405079) | Cod sursa (job #1486743) | Cod sursa (job #610594)
Cod sursa(job #610594)
#include<fstream>
#include<algorithm>
using namespace std;
int n,best[100010];
struct Spectacol{int x,y;};
Spectacol a[100010];
void Citire()
{
int i;
ifstream fin("heavymetal.in");
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i].x>>a[i].y;
fin.close();
}
int CautareBinara(int x,int capat)
{
int st,dr,m;
st=1; dr=capat;
while(st<=dr)
{
m=(st+dr)/2;
if(a[m].y<=x && a[m+1].y>x)
return m;
if(a[m].y<=x)
st=m+1;
else dr=m-1;
}
return 0;
}
inline bool Ordonare(Spectacol A,Spectacol B)
{
return A.y<B.y;
}
void Rezolvare()
{
int i,poz;
sort(a+1,a+n+1,Ordonare);
best[1]=a[1].y-a[1].x;
for(i=2;i<=n;i++)
{
poz=CautareBinara(a[i].x,i-1);
best[i]=max(best[i-1],best[poz]+a[i].y-a[i].x);
}
}
void Afisare()
{
ofstream fout("heavymetal.out");
fout<<best[n]<<"\n";
fout.close();
}
int main()
{
Citire();
Rezolvare();
Afisare();
return 0;
}