Pagini recente » Cod sursa (job #1521915) | Cod sursa (job #774285) | Cod sursa (job #1333949) | Cod sursa (job #2616477) | Cod sursa (job #446821)
Cod sursa(job #446821)
using namespace std;
#include<fstream>
#include<algorithm>
#define mk make_pair
#define x first
#define y second
const int MAX_N = 100007;
pair<int, int> A[MAX_N];
int N, bst[MAX_N];
struct cmp
{
bool operator()(const pair<int, int> &a, const pair<int, int> &b)const
{
return (a.y == b.y)?( a.x < b.x ):(a.y < b.y);
}
};
inline int intersect(pair<int, int> A, pair<int, int>B)
{
if( B.y <= A.x ) return 0;
return 1;
}
int main()
{
ifstream in("heavymetal.in"); ofstream out("heavymetal.out");
int i, j, a, b;
in>>N;
for(i = 1; i <= N; ++i)
{
in>>a>>b;
A[i] = mk(a,b);
}
sort(A+1, A+N+1, cmp());
bst[1] = A[1].y - A[1].x;
for(j = 1, i = 2; i <= N; ++i)
{
bst[i] = max(bst[i-1], A[i].y - A[i].x );
while(j && intersect( A[i], A[j] )) --j;
while( !intersect( A[i], A[j] ) )
bst[i] = max( bst[i], bst[j] + A[i].y - A[i].x ), ++j;
}
out<<bst[N]<<"\n";
return 0;
}