Pagini recente » Cod sursa (job #2043211) | Cod sursa (job #238131) | Cod sursa (job #1452678) | Cod sursa (job #1643727) | Cod sursa (job #1061360)
#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;
}
}
g<<cost[n];
return 0;
}