Pagini recente » Cod sursa (job #215875) | Cod sursa (job #1456024) | Cod sursa (job #150861) | Cod sursa (job #2065498) | Cod sursa (job #2561846)
#include <fstream>
#include <algorithm>
using namespace std;
struct kys {int x,y;};
kys v[100002];
long long n,i,s[100002],j,cmax;
int comp (kys a,kys b)
{
return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
int cb (int dr,int p)
{
int st=1,mid;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[mid].y<=p){st=mid+1;}
else{dr=mid-1;}
}
return st-1;
}
ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");
int main()
{
in>>n;
for(i=1;i<=n;i++)
{
in>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,comp);
s[1]=v[1].y-v[1].x;
for(i=2;i<=n;i++)
{
j=cb(i-1,v[i].x);
if(s[i-1]>=s[j]+v[i].y-v[i].x)
{
s[i]=s[i-1];
}
else{s[i]=s[j]+v[i].y-v[i].x;}
}
out<<s[n];
return 0;
}