Pagini recente » Cod sursa (job #2358167) | Cod sursa (job #2662896) | Cod sursa (job #646855) | Cod sursa (job #2661476) | Cod sursa (job #1224284)
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
#define NMAX 100001
struct trupa {
int x,y;
bool operator < (const trupa &c) const {
if(y==c.y)
return x<c.x;
return y<c.y;
}
};
trupa v[NMAX];
int t[NMAX];
int cbin(int p, int q, int x)
{
int sol,mij;
sol=0;
while(p<=q) {
mij=(p+q)/2;
if(v[mij].y<=x) {
sol=mij;
p=mij+1;
}
else q=mij-1;
}
return sol;
}
int main ()
{
int n,i,poz;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
f.close();
sort(v+1,v+n+1);
t[1]=v[1].y-v[1].x;
for(i=2;i<=n;i++) {
poz=cbin(1,i-1,v[i].x);
t[i]=max(t[poz]+v[i].y-v[i].x,t[i-1]);
}
g<<t[n];
g.close();
return 0;
}