Pagini recente » Cod sursa (job #2974353) | Cod sursa (job #1261546) | Cod sursa (job #3209915) | Cod sursa (job #1614605) | Cod sursa (job #1061349)
#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);
//initializezi cost[1]
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] altfel nu merge cautarea binare; intervalul i poate sa nu participe la solutie dar
// tu preiei valoarea din intervalul anterior
cost[i]=cost[i-1];
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);
if(Max < cost[i])
Max=cost[i];
st=mij+1;
}
else
dr=mij-1;
}
}
g<<Max;
return 0;
}