Pagini recente » Cod sursa (job #426500) | Cod sursa (job #2052931) | Cod sursa (job #3148657) | Cod sursa (job #492637) | Cod sursa (job #2581894)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct band
{
int start, fin;
int t;
}a[100009];
int n;
void Read()
{
int i;
fin >> n;
for(i=1; i<=n; ++i)
fin >> a[i].start >> a[i].fin;
}
bool cr(band a, band b)
{
///ordonam crescator dupa timpul de inceput si daca timpurile de inceput sunt egale sortam crescator dupa timpul de final
return a.fin < b.fin || a.fin == b.fin && a.start < b.start;
}
int CB(int st, int dr, int x)
{
int poz=0, m;
while(st<=dr)
{
m = (st+dr)/2;
if(a[m].fin <= a[x].start)
{
poz = m;
st = m + 1;
}
else dr = m - 1;
}
return poz;
}
void Solve()
{
int i, vmax=0, poz;
sort(a+1, a+n+1, cr);
a[1].t = a[1].fin - a[1].start;
for(i=2; i<=n; ++i)
{
a[i].t = a[i-1].t;
poz = CB(1,i,i); ///vedem la cine dinainte poate fi adaugat
//cout << poz << " " ;
a[i].t =max(a[i].t, a[poz].t + (a[i].fin - a[i].start));
}
for(i=1; i<=n; ++i)
if(a[i].t > vmax)
vmax = a[i].t;
fout << vmax << "\n";
}
int main()
{
Read();
Solve();
return 0;
}