Pagini recente » Cod sursa (job #913450) | Profil BlackNesta | Cod sursa (job #640271) | Cod sursa (job #364307) | Cod sursa (job #2541132)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
struct ura
{
int a,b;
};
ura v[100001];
int dp[100001];
bool cmp(ura x,ura y)
{
if (x.b>y.b)
return false;
else
return true;
}
int main ()
{
int n,i,l1,l2,poz,m;
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].a>>v[i].b;
sort (v+1,v+n+1,cmp);
for (i=1;i<=n;i++)
{
l1=1;
l2=i-1;
poz=0;
while (l1<=l2)
{
m=(l1+l2)/2;
if (v[m].b<=v[i].a)
{
poz=m;
l1=m+1;
}
else
l2=m-1;
}
if (dp[i-1]>dp[poz]+v[i].b-v[i].a)
dp[i]=dp[i-1];
else
dp[i]=dp[poz]+v[i].b-v[i].a;
}
fout<<dp[n];
return 0;
}