Pagini recente » Cod sursa (job #1388698) | Cod sursa (job #1352533) | Cod sursa (job #757007) | Cod sursa (job #2922306) | Cod sursa (job #1061372)
#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] se initializeaza cu cost[i-1] in cazul in care este mai mare decat trupe[i].sf-trup[i].inc; altfel nu merge cautarea binara; intervalul i poate sa nu participe la solutie dar
// tu preiei valoarea din intervalul anterior
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;
}