Pagini recente » Cod sursa (job #1586781) | Cod sursa (job #2633384) | Cod sursa (job #2555222) | Cod sursa (job #2479250) | Cod sursa (job #2378772)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int N=100004;
struct interval
{
int in,sf;
}v[N];
bool cmp(interval a , interval b)
{
return a.sf < b.sf;
}
int cautbin(int a)
{
int st,dr,max1=0,x;
st=1;
dr=v[a].in;
while(st<dr)
{
x=(st+dr)/2;
if(v[x].sf<=v[a].in)
{
if(x>max1)
{
max1=x;
}
st=x;
}
else
{
dr=x;
}
}
return max1;
}
int d[N];
int main()
{
int n,i,x;
in>>n;
for(i=1 ; i<=n ; i++)
{
in>>v[i].in>>v[i].sf;
}
sort(v+1,v+n+1,cmp);
d[1]=v[1].sf-v[1].in;
for(i=2 ; i<=n ; i++)
{
x=cautbin(i);
d[i]=max(d[i-1],d[x]+v[i].sf-v[i].in);
}
out<<d[n];
return 0;
}