Pagini recente » Cod sursa (job #364524) | Cod sursa (job #183762) | Cod sursa (job #1372280) | Cod sursa (job #1257979) | Cod sursa (job #446880)
Cod sursa(job #446880)
using namespace std;
#include<fstream>
#include<algorithm>
#include<vector>
#define mk make_pair
#define x first
#define y second
const int MAX_N = 100007;
pair<int, int> A[MAX_N], B[MAX_N];
int N, bst[MAX_N], V[MAX_N*2], P, H[2*MAX_N];
vector<int>G[2*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);
}
};
int main()
{
ifstream in("heavymetal.in"); ofstream out("heavymetal.out");
int i, j, a, b, k;
in>>N;
for(i = 1; i <= N; ++i)
{
in>>a>>b;
A[i] = mk(a,b);
H[++P] = a, H[++P] = b;
}
sort( A + 1, A + N + 1, cmp());
sort( H + 1, H + P + 1 );
V[1] = 1;
for(i = 2, P = 1; i <= 2*N; ++i)
if( H[i] != H[i-1] ) V[++P] = H[i];
for(i = 1; i <= N; ++i)
{
a = lower_bound( V + 1, V + P + 1, A[i].x ) - V;
b = lower_bound( V + 1, V + P + 1, A[i].y ) - V;
B[i] = mk(a,b);
G[b].push_back(i);
}
for(i = 1; i <= 2*N; ++i)
{
bst[i] = bst[i-1];
for(k = 0; k < G[i].size(); ++k)
{
j = G[i][k];
bst[i] = max( bst[i], bst[ B[j].x ] + A[j].y - A[j].x );
}
}
out<<bst[2*N]<<"\n";
return 0;
}