Pagini recente » Cod sursa (job #1247486) | Cod sursa (job #666876) | Cod sursa (job #1461298) | Cod sursa (job #634745) | Cod sursa (job #1761457)
#include <fstream>
#include<algorithm>
using namespace std;
struct trupa{ int x,y,l;} T[100001];
int n,P[100001];
long long V[100001];
struct cmp{
bool operator() (int a, int b)
{
return T[a].y < T[b].y or (T[a].y == T[b].y and T[a].x < T[b].x);
}
};
int caut_bin(int poz)
{
int st = 1, dr = poz, m;
while (st < dr)
{
m = (st + dr) / 2;
if (T[P[m]].y > T[P[poz]].x) dr = m;
else st = m + 1;
}
m = (st + dr) / 2;
if (T[P[m]].y > T[P[poz]].x) -- m;
return m;
}
int main()
{
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
fin >> n;
for(int i = 1; i <= n; i++)
{
fin>>T[i].x>>T[i].y;
T[i].l = T[i].y - T[i].x;
P[i]=i;
}
sort(1+P, 1+n+P, cmp());
V[1]=T[P[1]].l;
for(int i = 2; i <= n; i++)
{
int ant = caut_bin(i);
V[i] = max (V[i-1], V[ant] + T[P[i]].l);
}
fout << V[n] << '\n';
fout.close();
return 0;
}