Pagini recente » Cod sursa (job #463890) | Cod sursa (job #469078) | Cod sursa (job #1187394) | Cod sursa (job #961632) | Cod sursa (job #1726931)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, sol[100000];
pair <int, int> v[100000];
void Read()
{
int i, x, y;
fin >> n;
for(i = 1; i <= n; i++)
{
fin >> x >> y;
v[i] = make_pair(x, y);
}
fin.close();
}
int CB(int p)
{
int st, dr, x, m, poz;
st = 1;
dr = p - 1;
x = v[p].first;
while(st <= dr)
{
m = (st + dr) / 2;
if(v[m].second <= x)
{
poz = m;
st = m + 1;
}
else dr = m - 1;
}
return poz;
}
inline void Solve()
{
int i;
sort(v + 1, v + 1 + n);
for(i = 1; i <= n; i++)
sol[i] = max(sol[i - 1], sol[CB(i)] + (v[i].second - v[i].first));
fout << sol[n] << "\n";
fout.close();
}
int main()
{
Read();
Solve();
return 0;
}