Pagini recente » Cod sursa (job #491228) | Cod sursa (job #2738048) | Cod sursa (job #644415) | Cod sursa (job #1869416) | Cod sursa (job #1724202)
#include <bits/stdc++.h>
#define nmax 100050
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct interval
{
int x, y;
};
interval a[nmax];
int n, b[nmax];
inline bool cmp(const interval A, const interval B)
{
if(A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
int CB(int p)
{
int st, dr, x, m, poz = 0;
st = 1;
dr = p - 1;
x = a[p].x;
while(st <= dr)
{
m = (st + dr) / 2;
if(a[m].y <= x)
{
poz = m;
st = m + 1;
}
else dr = m - 1;
}
return poz;
}
int main()
{
int i, poz;
f >> n;
for(i = 1; i <= n; i++)
f >> a[i].x >> a[i].y;
f.close();
sort(a + 1, a + n + 1, cmp);
for(i = 1; i <= n; i++)
{
b[i] = b[i - 1];
poz = CB(i);
b[i] = max(b[i],b[poz] + (a[i].y - a[i].x));
}
g << b[n] << "\n";
g.close();
return 0;
}