Pagini recente » Cod sursa (job #2714487) | Cod sursa (job #476380) | Cod sursa (job #511846) | Cod sursa (job #2009001) | Cod sursa (job #1223060)
#include<fstream>
#include<algorithm>
using namespace std;
typedef struct { int x,y; } tip;
tip a[100005];
int i,j,n,sol[100005];
bool cmp(tip a, tip b) {
if (a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
int main(void) {
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
fin>>n;
for (i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
sol[n]=a[n].y-a[n].x;
for (i=n-1; i>=1; --i) {
int l=i+1,r=n;
while (l<=r) {
int mid=(l+r)/2;
if (a[mid].x<a[i].y) l=mid+1;
else r=mid-1;
}
sol[i]=max(sol[i+1],a[i].y-a[i].x+sol[l]);
}
fout<<sol[1];
return 0;
}