Pagini recente » Cod sursa (job #907932) | Cod sursa (job #1520049) | Cod sursa (job #1618130) | Cod sursa (job #635664) | Cod sursa (job #2150156)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX=10000;
int d[NMAX+5];
struct timp
{
int inc, sf;
};
timp v[NMAX+5];
bool cmp(timp a, timp b)
{
if(a.sf==b.sf)
{
return a.inc<=b.inc;
}
else
return a.sf<=b.sf;
}
int main()
{
int n, i, tc, st, dr, mid;
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].inc>>v[i].sf;
sort(v+1,v+n+1, cmp);
d[1]=v[1].sf-v[1].inc;
for(i=2;i<=n;i++)
{
tc=v[i].inc;
st=1;
dr=i-1;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[mid].sf<=tc)
st=mid+1;
else
dr=mid-1;
}
d[i]=max(v[i].sf-v[i].inc+d[dr], d[i-1]);
}
fout<<d[n]<<"\n";
return 0;
}