Pagini recente » Cod sursa (job #1546021) | Cod sursa (job #1119029) | Cod sursa (job #3125872) | Cod sursa (job #2811425) | Cod sursa (job #1726937)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, sol[100005];
struct timp
{
int x, y;
};
timp v[100005];
inline bool cmp(const timp A, const timp B)
{
if(A.y == B.y) return A.x < B.x;
return A.y < B.y;
}
void Read()
{
int i;
fin >> n;
for(i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
fin.close();
}
int CB(int p)
{
int st, dr, x, m, poz;
st = 1;
dr = p - 1;
x = v[p].x;
poz = 0;
while(st <= dr)
{
m = (st + dr) / 2;
if(v[m].y <= x)
{
poz = m;
st = m + 1;
}
else dr = m - 1;
}
return poz;
}
inline void Solve()
{
int i;
sort(v + 1, v + 1 + n, cmp);
for(i = 1; i <= n; i++)
sol[i] = max(sol[i - 1], sol[CB(i)] + (v[i].y - v[i].x));
fout << sol[n] << "\n";
fout.close();
}
int main()
{
Read();
Solve();
return 0;
}