Pagini recente » Cod sursa (job #3347440) | Cod sursa (job #2873100) | Cod sursa (job #336048) | Cod sursa (job #3348545) | Cod sursa (job #3318261)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
#define N 100001
struct concert
{
int start, finish;
}a[N];
int n, pd[N], t[N];
void citire()
{
fin >> n;
for(int i = 1; i <= n; i++)
fin >> a[i].start >> a[i].finish;
}
bool cmp(concert x, concert y)
{
return x.finish < y.finish;
}
void timp()
{
for(int i = 1; i <= n; i++)
t[i] = a[i].finish - a[i].start;
}
int cb(int i)
{
int st = 1, dr = i - 1, rez = 0;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(a[mij].finish <= a[i].start)
{
rez = mij; // mij este candidat valid
st = mij + 1;
}
else
dr = mij - 1;
}
return rez;
}
void dp()
{
pd[0] = 0;
for(int i = 1; i <= n; i++)
{
int j = cb(i);
pd[i] = max(pd[i - 1], t[i] + pd[j]);
}
}
int main()
{
citire();
sort(a + 1, a + n + 1, cmp);
/*for(int i = 1; i <= n; i++)
fout << a[i]. start << " " << a[i].finish << "\n";*/
timp();
dp();
fout << pd[n];
return 0;
}