Pagini recente » Cod sursa (job #1620118) | Cod sursa (job #2474734) | Cod sursa (job #1650173) | Cod sursa (job #1457739) | Cod sursa (job #1061363)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct trupa
{
int inc, sf;
}trupe[100001];
bool compara( trupa t1, trupa t2)
{
return t1.sf < t2.sf;
}
int n, i, j, dr, st, mij, sol, cost[100001], Max=-1;
int main()
{
f>>n;
for (i=1; i<=n; i++)
{
f>>trupe[i].inc>>trupe[i].sf;
}
sort(trupe + 1, trupe + n + 1, compara);
cost[1]=trupe[1].sf-trupe[1].inc;
Max=cost[1];
for (i=2; i<=n; i++)
{
st=1;
dr=i-1;
cost[i]=max(cost[i-1],trupe[i].sf-trupe[i].inc);
while (st<=dr)
{
mij=(st+dr)/2;
if (trupe[i].inc >= trupe[mij].sf)
{
cost[i]=max(cost[i], cost[mij] + trupe[i].sf - trupe[i].inc);
st=mij+1;
}
else
dr=mij-1;
}
if(Max<cost[i])
Max=cost[i];
}
g<<Max;
return 0;
}