Pagini recente » Cod sursa (job #911415) | Cod sursa (job #2603125) | Cod sursa (job #2070999) | Cod sursa (job #2702305) | Cod sursa (job #2553902)
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
struct intervale{
int inc, sf;
}it[100001];
int n, maxime_partiale[100001];
int cautare_binara_st(int ind)
{
int st, dr, mijl, p;
st = 1;
dr = ind-1;
p = 0;
while (st<= dr)
{
mijl = (st + dr)/2;
if (it[mijl].sf < it[ind].inc)
{
p = mijl;
st = mijl+1;
}
else
{
if(it[mijl].sf == it[ind].inc)
return mijl;
else
{
if(it[mijl].sf > it[ind].inc)
dr = mijl-1;
}
}
}
return p;
}
int conditie(intervale el1, intervale el2)
{
// if(el1.sf > el2.sf)
// return el1 > el2;
// if(el1.sf == el2.sf)
// {
// if(el1.inc > el2.inc)
// return el2 > el1;
// return el1 > el2;
// }
return el1.sf < el2.sf;
}
int main()
{
int i, p;
fin >> n;
for (i= 1; i<= n; i++)
fin >> it[i].inc >> it[i].sf;
//sortam intervalele crescator dupa sfarsituri
sort(it + 1, it+n+1, conditie);
for(i = 1; i<= n; i++)
{
p = -1;
p = cautare_binara_st(i);
if(maxime_partiale[p] + (it[i].sf - it[i].inc) > maxime_partiale[i-1])
maxime_partiale[i] = maxime_partiale[p] + (it[i].sf - it[i].inc);
else
maxime_partiale[i] = maxime_partiale[i-1];
}
fout << maxime_partiale[n];
return 0;
}