Pagini recente » Cod sursa (job #2841242) | Cod sursa (job #2957048) | Cod sursa (job #1104883) | Cod sursa (job #397724) | Cod sursa (job #1060871)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct trupa
{
int inc, sf;
}trupe[1001];
bool compara(const trupa &t1, const trupa &t2)
{
if(t1.sf==t2.sf)
{
return t1.inc > t2.inc;
}
return t1.sf < t2.sf;
}
int n, i, j, dr, st, mij, sol, cost[1001], 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);
for (i=2; i<=n; i++)
cost[i]=0;
cost[1]=trupe[1].sf - trupe[1].inc;
for (i=2; i<=n; i++)
{
st=1;
dr=i;
cost[i]=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] + cost[i]);
if(Max < cost[i])
Max=cost[i];
st=mij+1;
}
else
dr=mij-1;
}
}
g<<Max;
return 0;
}